2
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for this! But then, can I also say that here we already have bijection too? $\endgroup$
    – mmt
    May 7, 2013 at 13:08
  • $\begingroup$ 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. $\endgroup$
    – Jing Zhang
    May 7, 2013 at 17:13
  • $\begingroup$ Sorry for not being clear enough, but what I'm asking is whether we can construct a bijection once we have the injection, without any further jump. At the first jump, having the bijection we have the least natural number that is uniquely associated with a computable real, and we can find the "next" natural number uniquely associated with anther computable real, and so on. Don't we then effectively have a bijection? Or in short, only one jump is enough for obtaining a bijection? $\endgroup$
    – mmt
    May 9, 2013 at 1:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .