# Injection from computable numbers into natural numbers

Each Turing machine which writes an infinite sequence of 1 and 0 can be regarded as representing a (computable) real number (and of course each Turing machine represents a natural number by its machine table, or program). The question is, how many Turing jumps do we need to construct an injection from such computable numbers into natural numbers. Since there are an infinite number of Turing machines that compute one and the same computable real number, it seems we need at least one Turing jump. Is only once is enough? If not, how many? Even transfinite times?

• I recommend that you show here why one jump suffices. Apr 29, 2013 at 16:55

I believe one Turing jump suffices. Each computable real could be represented by a {0,1}-Turing machine therefore they are no more than the total number of computer programs. Consider the map $f: \omega-K \mapsto \omega$ where $K$ is the halting set, that is set of the indices of all programs that halt. Then $f(x)=least \ e\in \omega$ such that $\exists z \varphi_e(z)\neq \varphi_i(z) \forall i<e$. This is a $\Sigma_1^0$ question thus can be answer in $\emptyset'$. Then it is easy to see the construction of f is recursive in $K$ and it is injective also.
• It is not necessarily a bijection. Since we could choose the numberings of programs in whatever way we want, we could let $\varphi_0=\varphi_1$, then 1 is never likely to be in the range since it does not satisfy the requirement of f. For one program of the same functionality we could have infinitely many indices (since we could just add some redundant words into the body of the program), therefore, f is not surjective. May 7, 2013 at 17:13