Computable function =================== Computable functions are the basic objects of study in computability theory. Informally, a function is computable if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precise definition of the concept of algorithm, every formal definition of computability must refer to a specific model of computation. Many such models of computation have been proposed, the major ones being Turing machines, register machines, lambda calculus and general recursive functions. Although these four are of a very different nature, they provide exactly the same class of computable functions, and, for every model of computation that has ever been proposed, the computable functions for such a model are computable for the above four models of computation. The Church–Turing thesis is the unprovable assertion that every notion of computability that can be imagined can compute only functions that are computable in the above sense. Before the precise definition of computable functions, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time).… Computable functions are the basic objects of study in computability theory. Informally, a function is computable if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precise definition of the concept of algorithm, every formal definition of computability must refer to a specific model of computation. Many such models of computation have been proposed, the major ones being Turing machines, register machines, lambda calculus and general recursive functions. Although these four are of a very different nature, they provide exactly the same class of computable functions, and, for every model of computation that has ever been proposed, the computable functions for such a model are computable for the above four models of computation. The Church–Turing thesis is the unprovable assertion that every notion of computability that can be imagined can compute only functions that are computable in the above sense. Before the precise definition of computable functions, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently. 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 computing the value of a function is known as a function problem, by contrast to decision problems whose results are either "yes" or "no". ==Definition== Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an effective procedure. With more rigor, a function f:\mathbb N^k\rightarrow\mathbb N is computable if there is an effective procedure that, given any -tuple \mathbf x of natural numbers, will produce the value f(\mathbf x) . In agreement with this definition, the remainder of this article presumes that computable functions take finitely many natural numbers as arguments and produce a value that is a single natural number. As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent models of computation, including Turing machines General recursive functions Lambda calculus Post machines (Post–Turing machines and tag machines). Register machines Although these models use different representations for the functions, their inputs, and their outputs, translations exist between any two models, and so every model describes essentially the same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow. These functions are sometimes referred to as "recursive", to contrast with the informal term "computable", a distinction stemming from a 1934 discussion between Kleene and Gödel. For example, one can formalize computable functions as μ-recursive functions, which are partial functions that take finite tuples of natural numbers and return a single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is closed under composition, primitive recursion, and the μ operator. Equivalently, computable functions can be formalized as functions that can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function f:\mathbb N^k\rightarrow\mathbb N can be calculated if there exists a computer program with the following properties: If f(\mathbf x) is defined, then the program will terminate on the input \mathbf x with the value f(\mathbf x) stored in the computer memory. If f(\mathbf x) is undefined, then the program never terminates on the input \mathbf x . ==Examples== The following functions are computable: Each function with a finite domain; e.g., any finite sequence of natural numbers. Each constant function f : N k → N, f(n 1 ,...n k ) := n. Addition f : N 2 → N, f(n 1 ,n 2 ) := n 1 + n 2 The greatest common divisor of two numbers A Bézout coefficient of two numbers The smallest prime factor of a number If f and g are computable, then so are: f + g, f * g, \color{Blue} f \circ g if f is unary, max(f,g), min(f,g), and many more combinations. The following examples illustrate that a function may be computable though it is not known which algorithm computes it. The function f such that f(n) = 1 if there is a sequence of at least 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 n (n) + 1 (where f n is n-th function by this enumeration) by invoking the Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound, but the total function it computes cannot be any of the functions proven total by the proof system, otherwise there would be some n for which f n (n) + 1 = f n (n). ==Extensions of computability== ===Relative computability=== The notion of computability of a function can be relativized to an arbitrary set of natural numbers A. A function f is defined to be computable in A (equivalently A-computable or computable relative to A) when it satisfies the definition of a computable function with modifications allowing access to A as an oracle. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation that asks whether a given integer is a member of A. We can also talk about f being computable in g by identifying g with its graph. ===Higher recursion theory=== Hyperarithmetical theory studies those sets that can be computed from a computable ordinal number of iterates of the Turing jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second-order arithmetic and to some models of hypercomputation. 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. ===Hyper-computation=== 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 models of computation that go beyond normal Turing computation. ==References== Cutland, Nigel. Computability. Cambridge University Press, 1980. 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. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), p.230–265. Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965. REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Computable function}, url = {https://encyclopegia.org/a/computable-function} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Computable function UR - https://encyclopegia.org/a/computable-function ER - CITE THIS ARTICLE ---------------- Cite this article: Computable function Derived from: https://en.wikipedia.org/w/index.php?oldid=1339844853 Licence: CC BY-SA 4.0 Snapshot: enwiki-001339844853 Permalink: /a/computable-function