FANDOM


The proof that \(\Sigma >^*\) all computable functions is nontrivial but straightforward. I thought I would share it.

Theorem. \(\Sigma >^* f\) for all computable \(f : \mathbb{N} \rightarrow \mathbb{N}\).

Proof. We first establish a convention that the inputs and outputs to our Turing machines are nonnegative integers in the form of consecutive blocks of ones in otherwise blank tapes. The Turing machine must start on the rightmost one in input, and it must halt on the rightmost one in output.

Given a computable \(f\), define \(F\) as

\[F(n) = \sum_{i = 0}^n (f(i) + i^2).\]

We see that \(F(n) \geq f(n)\) and \(F(n) \geq n^2\), and that \(F\) is computable and increasing. Therefore there is a Turing machine \(M_F\) that computes \(F\) — say it has \(C\) non-halting states. Also consider a Turing machine \(M_n\) that computes \(n\) given blank input that has \(n\) non-halting states. By composing the Turing machines \(M_n \rightarrow M_F \rightarrow M_F\) we get a Turing machine \(M\) that computes \(F(F(n))\) in \(n + 2C\) non-halting states given blank input. \(M\) is a busy beaver contender for \(n + 2C\) states, so \(\Sigma(n + 2C) \geq F(F(n))\). Since \(F(n) \geq n^2\) and \(n^2 >^* n + 2C\), \(F(n) >^* n + 2C\). It follows from the monotonicity of \(F\) that \(F(F(n)) >^* F(n + 2C)\), so \(\Sigma(n + 2C) >^* F(n + 2C)\). Since \(F \geq f\), \(\Sigma(n + 2C) >^* f(n + 2C)\). Therefore \(\Sigma >^* f\). Q.E.D.

The above should be fairly accessible to anyone who has done some work with TM programming.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.