Computable function

View full site to see MathJax equation

"Recursive" redirects here. You may be looking for recursion.

A computable function (or recursive function) is a partial computable function that is total. That is, a computable function is a function that can be computed with a Turing machine. A function \(f: \mathbb{N} \to \mathbb{N}\) which is not computable is called uncomputable.

Suppose we have a two-color Turing machine \(T\). Given a positive integer \(n\), we set the tape to be blank except for \(n\) consecutive ones with the leftmost one at the position of the TM head. We simulate the Turing machine, and one of the following happens:

It halts with \(m \in \mathbb{N}\) consecutive ones on the tape, with the head positioned on the leftmost one. In this case we say that \(T\) outputs \(m\) given input \(n\).
It halts, but it does not have the configuration described above.
It does not halt.

Let \(f\) be the set of all ordered pairs \((m,n)\) for which \(T\) outputs \(m\) given input \(n\). We can see that \(f\) is a partial function with domain space and codomain \(\mathbb{N}\). We say that \(T\) computes \(f\), and a partial computable function (or partial recursive function) is a partial function for which there exists a Turing machine that computes it.

An uncomputable function may (euphemistically) refer to an uncomputably fast-growing function. There exist functions that eventually dominate all computable functions, the most famous example being the busy beaver function. Such functions are necessarily uncomputable, and grow exceptionally fast. It is important to note that not all uncomputable functions have this property - an example would be the function \(h(n)\) defined as \(1\) if the \(n\)th (in some fixed ordering) Turing machine halts, and \(0\) otherwise.

Note that the uncomputability of a given function is generally very difficult. For example, given an uncomputable function \(f(n)\) such as \(\Sigma(n)\), we usually do not have an obvous way to compute \(f(n) \mod 2\), but it does not imply its uncomputability. For example, when \(f(n)\) is given as \(2 \Sigma(n)\), then it is easy to show \(f(n) \mod 2 = 0\), and hence \(f(n) \mod 2\) is computable.

Intuitively, "almost all" functions over the natural numbers are uncomputable — there are countably many computable functions and uncountably many functions over the natural numbers.

Properties of computable functions[]

Theorem: The set of computable functions is closed under composition.

Proof: Given computable \(f\) and \(g\), we wish to show that \(g \circ f\) is computable. Let \(S\) be a Turing machine that computes \(f\), and \(T\) a Turing machine that computes \(g\), such that the states of \(S\) and \(T\) are disjoint. Let \(Q_S\) be the states of \(S\), Let \(q_{S0}\) be the initial state, let \(q_{SH}\) be the halting state, let \(\delta_S\) be the transition function, and like so for \(T\). Then define the Turing machine \(S \circ T\) like so:

\(Q_{S \circ T} = (Q_S \backslash q_{SH}) \cup Q_T\)
\(q_{S \circ T,0} = q_{S0}\)
\(q_{S \circ T,H} = q_{TH}\)
\(\delta_{S \circ T} = \delta_S' \cup \delta_T\) where \(\delta_S'\) replaces all instances of \(q_{SH}\) in \(\delta_S\) with \(q_{T0}\).
\(Q_{S \circ T} \leadsto Q_{q_{SN} \delta^{\beta}}\) for \(N\) does not \( >^*S\) and \(\beta\) is computable.Thus the whole sequence is computable.

Since this Turing machine effectively computes \(f\) and then \(g\), its associated computable function is \(g \circ f\). Therefore \(g \circ f\) is computable.

∎

Notable uncomputable functions[]

Currently, most uncomputably fast-growing functions are derived from the busy beaver or the Rayo function.

Uncomputable number[]

In googology, the terms computable number and uncomputable number are often used. They have no strict mathematical definitions, but intuitively, if \(x\) is called a computable number, then usually there is a pair (n,f) of a meta-theoretic natural number \(n\) and a computable function \(f\) whose code with respect to a fixed encoding is also a meta-theoretic natural number such that the statement \(f(n) = x\) is provable in ZFC set theory. Uncomputable number then, is a number that is not computable. Note that the notion of computable number in googology does not coincide with that in mathematics, which means a computable real number. Every natural number is a computable real number, and hence it is irrelevant to the terminology in googology.

Computable function

Contents

Properties of computable functions[]

Notable uncomputable functions[]

Uncomputable number[]

See also[]

Fan Feed