|
Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. They make precise the intuitive notion of algorithm. Computable functions can be used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Their definition, however, must make reference to some specific model of computation. Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. ...
An artistic representation of a Turing Machine . ...
In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. ...
Before the precise definition of computable function mathematicians often used the informal term effectively computable. This term has since come to be identified with the computable functions. Although these functions are called effective, they may be extremely inefficient. The fields of feasible computability and computational complexity study functions that can be computed efficiently. Leonhard Euler is considered by many to be one of the greatest mathematicians of all time A mathematician is the person whose primary area of study and research is the field of mathematics. ...
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
According to the Church-Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable. In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem. In computational complexity theory the Blum axioms or Blum complexity axioms are axioms which specify desirable properties of complexity measures on the set of computable functions. ...
As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...
In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem...
Definition
The computable functions are finitary partial functions on the natural numbers. Each computable function f takes a fixed number of natural numbers as arguments; different functions may take different numbers of arguments. Because the functions are partial, they may not be defined for every possible choice of input. If a computable function is defined then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). The notation  indicates that the partial function f is defined on arguments  , and the notation  indicates that f is defined on the arguments and the value returned is y. These functions are also called partial recursive functions. In computability theory, the domain of a function is taken to be the set of all inputs for which the function is defined. In mathematics or logic, a finitary operation is one, like those of arithmetic, that take a number of input values to produce an output. ...
In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
In mathematics a pairing function is a process to uniquely encode two natural numbers into a single natural number. ...
In mathematics, the domain of a function is the set of all input values to the function. ...
A function which is defined for all arguments is called total. If a computable function is total, it is called a total computable function or total recursive function. In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in...
There are many equivalent ways to define the class of computable functions. For concreteness, the remainder of this article will assume that computable functions have been defined as those partial functions that can be calculated by a Turing machine. There are many equivalent models of computation that define the same class of computable functions. These models of computation include An artistic representation of a Turing Machine . ...
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. ...
and others. An artistic representation of a Turing Machine . ...
In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
In theoretical computer science and recursion theory, a Post machine, named after Emil Leon Post, is a deterministic finite automaton with a queue. ...
In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. ...
Characteristics of computable functions - Main article: Algorithm
The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a compiler is able to read instructions in one computer language and emit instructions in another language. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
This article is about the computing term. ...
Enderton [1997] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.
- “There must be exact instructions (i.e. a program), finite in length, for the procedure.”
Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required. - “If the procedure is given a k-tuple x in the domain of f, then after a finite number of discrete steps the procedure must terminate and produce f(x).”
Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned. - “If the procedure is given a k-tuple x which is not in the domain of f, then the procedure might go on forever, never halting. Or it might get stuck at some point, but it must not pretend to produce a value for f at x.”
Thus if a value for f(x) is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is always correct when it produces an outcome.
Enderton goes on to list several requirements that are not made of the procedure for a computable function:
- The procedure must work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.
- The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.
- Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.
The field of computational complexity studies function with prescribed bounds on the time and/or space allowed in a successful computation. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
A partial function is computable if and only if it is recursive. In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ...
Computable sets and relations A set A of natural numbers is called computable (synonyms: recursive, decidable) if there is a computable function f such that for each number n,  if n is in A and  if n is not in A.
A set of natural numbers is called computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that for each number n, f(n) is defined if and only if n is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word enumerable is used because the following are equivalent for a nonempty subset B of the natural numbers:
- B is the domain of a computable function.
- B is the range of a total computable function. If B is infinite then the function can be assumed to be injective.
If a set B is the range of a function f then the function can be viewed as an enumeration of B, because the list f(0), f(1), ... will include every element of B. In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...
Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of computable relation and computably enumerable relation can be defined from their analogues for sets. In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...
Formal languages - Main article: Formal languages
In computability theory in computer science, it is common to consider formal languages. An alphabet is an arbitrary set. A word on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet {0,1}. A language is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet. In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...
In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ...
In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...
A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called computable (synonyms: recursive, decidable) if there is a computable function f such that for each word w over the alphabet,  if the word is in the language and  if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.
A language is computably enumerable (synonyms: recursively enumerable, semidecidable) if there is a computable function f such that f(w) is defined if and only if the word w is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers.
Examples The following functions are computable: - The function which gives the list of prime factors of a number.
If f and g are computable, then so are: f + g, f * g,  if f is unary, max(f,g), min(f,g), and many more combinations. In mathematics a constant function is a function whose values do not vary and thus are constant. ...
3 + 2 with apples, a popular choice in textbooks Addition is the basic operation of arithmetic. ...
In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...
In number theory, Bézouts identity, named after Étienne Bézout, is a linear diophantine equation. ...
In mathematics, a Diophantine equation is a polynomial equation that only allows the variables to be integers. ...
The following example illustrates that a function may be computable even if no explicit algorithm is known to compute it.
- The function f such that f(n) = 1 if there is a sequence of n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable.
The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if k ≤ n. Every such function is computable. Thus, despite the fact that it is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, the function f is computable.
Church-Turing thesis - Main article: Church-Turing thesis
The Church-Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church-Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis: In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
- Many equivalent models of computation are known, and they all give the same definition of computable function (or a weaker version, in some instances).
- No stronger model of computation which is generally considered to be effectively calculable has been proposed.
The Church-Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.
Uncomputable functions and unsolvable problems - Main article: List of undecidable problems
Because every computable function has a finite procedure telling how to compute it, there are only countably many computable functions. There are uncountably many finitary functions on the natural numbers, so most such functions are not computable. The Busy beaver function is a concrete example of such a function. In computability theory, an undecidable problem is a problem whose language is not a recursively enumerable set. ...
In computability theory, a Busy Beaver (from the colloquial expression for industrious person) is a Turing machine that, when given an empty tape, does a lot of work, then halts. ...
Similarly, most subsets of the natural numbers are not computable. The Halting problem was the first such set to be constructed. The Entscheidungsproblem, proposed by David Hilbert, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed that this set of natural numbers is not computable in the 1930s. According to the Church-Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...
The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ...
David Hilbert (January 23, 1862, Königsberg, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. ...
Extensions of computability The notion of computability of a function can be relativized to an arbitrary set of natural numbers A, or equivalently to an arbitrary function f from the naturals to the naturals, by using Turing machines (or any other model of computation) extended by an oracle for A or f. Such functions may be called A-computable or f-computable respectively. In computability theory relative computability or relativized computability is the study of computability concepts relative to a given set. ...
In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
An artistic representation of a Turing Machine . ...
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...
Although the Church-Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies a computability notion in which it is possible to perform infinitely many steps before producing a successful answer. Hyperarithmetical theory studies a different extension of standard computability. Even more general recursion theories have been studied, such as E-recursion theory in which any set can be used as an argument to an E-recursive function. Hypercomputation refers to various proposed methods for the computation of non-Turing-computable functions. ...
See also In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. ...
The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ...
Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ...
In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ...
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ...
References - Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
- Rogers, H. Theory of recursive functions and effective computation (McGraw-Hill 1967).
- Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.
|
Feeds |
Contact