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

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.

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} \mapsto \mathbb{N}\) which is not computable is called uncomputable.

An uncomputable function may (euphemistically) refer to an uncomputably fast-growing function. There exist functions that eventually dominates all computable functions, the most famous example being the busy beaver function. Such functions are necessarily uncomputable, and grow exceptionally fast, above the order of \(\omega_1^\text{CK}\) of the FGH. 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.

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.

See also