Computability Theory

The Computability Concept 17

Rado’s theorem (1962): The function σ is not Turing computable. Moreover, for any

Turing computable total function f , we have f (x) < σ (x) for all sufficiently large x.

That is, σ eventually dominates any Turing computable total function.

Proof. Assume we are given some Turing computable total f . We must show that σ

eventually dominates it. Define (for reasons that may initially appear mysterious) the

function g:

g(x) = max( f (2x), f (2x + 1)) + 1.

Then g is total and one can show that it is Turing computable. So there is some Turing

machine M with, say, k states that computes it, using the alphabet {1} and base-1

notation. ...