Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?

Question

In his celebrated paper, "On Computable Numbers, With An Application To the Entscheidungsproblem", Turing defines a "computable number" as follows:

The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means....According to my definition, a number is computable if its decimal can be written down by a machine.

Since it is known that the decimal expansions of $\pi$ and $e$ (for example) are infinitely long, isn't Turing's "Turing Machine" already an ITTM given Hamkins' and and Lewis' definition of an ITTM and Turing's definitions of circular and circle-free machines (where Hamkins' and Lewis' definition of "the configuration of the machine at stage $\omega$" is what one should expect to happen to a decimal expansion generated by a circle-free machine at that stage)?

Answer 1

No, classical computability theory as you point is quite capable of dealing with infinitary computable enumerations and computability-in-the-limit from its earliest stages. I believe that Turing is to be credited with the fundamental distinction between a computably decidable decision problem and one that is merely semi-decidable or computably enumerable. Namely, a computably decidable problem is one for which one can fully compute the answer, getting either the yes answer or the no answer on any given input. With the semi-decidable problems, in contrast, one can expect only the affirmative answers, with negative instances perhaps receding into infinite computation without any resolution.

Of course, a problem is semi-decidable in this sense if and only if the instances of the problem are computably enumerable in an infinite computation, in the sense that there is a computable procedure that prints out the positive instances on the tape. One can design a program that systematically considers any possible input for any definite possible amount of time, and enumerates any positive resolutions of the problem it finds. In this way, we see that a decision problem is semi-decidable if and only if it is computably enumerable.

Alan Turing proved of course that the halting problem was computably enumerable but not computably decidable. This is the canonical problem showing that these notions differ.

Meanwhile, computably enumeration is not the same as computable-in-the-limit. A binary sequence $s\in 2^{\mathbb{N}}$ is computable-in-the-limit if there is a computable procedure that will produce an output tape that on each cell stabilizes on the values of $s$. That is, each cell of the output tape changed only finitely often. This is not quite the same thing as as a computable enumeration of $s$, since the computable procedure might change its its mind about the values of $s(k)$, but for each $k$ only finitely often, so as to stabilize point-wise in the limit.

Theorem. The following are equivalent for any infinite binary sequence $s\in 2^{\mathbb{N}}$.

1. $s$ is computable in the limit.
2. $s$ is Turing computable from the halting problem.
3. $s$ has complexity $\Delta_2$ in the arithmetic hierarchy.

Proof. If $s$ is computable-in-the-limit, then $s$ is computable from the halting problem, since at any stage in the computable procedure to produce $s$, we can ask whether the digit $k$ will change or not, and the halting problem will know the answer. By waiting until the digits will not change, we can thereby know the true digits of $s$.

If $s$ is computable from the halting problem, then by computing approximations to the halting problem, by waiting for programs to halt, we can get better and better approximations to that oracle, and thereby produce better and better approximations to $s$, which will stabilize digitwise. This shows $1\iff 2$.

If $s$ is computable from the halting problem, then $s(k)=1$ if and only if every sufficiently long approximation to the halting problem reveals that the algorithm produces a $1$ in digit $k$. This is a $\Pi_2$ definition. For a $\Sigma_2$ definition, we observe that $s(k)=1$ if and only if there is computation from a version of the halting problem revealed as correct at that stage, such that it is never improved. So (2) implies (3).

And if $s$ is $\Delta_2$ definable, then we can compute $s$ from the halting problem as an oracle, since $s(k)=1$ just in case $\exists n\forall m\varphi(n,m,k)$, where $\varphi$ has bounded quantifiers, and so we can search for a $n$, and ask the halting problem whether every $m$ will have $\varphi(n,m,k)$, and similarly for $s(k)=0$, so from the halting problem we can determine what is $s(k)$. ​$\Box$

In this sense, your observation that computably enumerable sets are computable in the limit is completely right. But the latter concept is actually strictly more powerful, since not every $\Delta_2$ set is enumerable. For example, the complement of the halting problem is computable in the limit, but not enumerable.

Meanwhile, Turing had indeed defined that a computable real number is one for which there is a computable procedure to enumerate its decimal digits. This is true as far as it goes, but this definition is no longer used as the definition of computable number, as I explain in my blog post, Alan Turing on computable numbers, which David Roberts had mentioned in the comments. Namely, in the contemporary analysis, we usually say that a real number $r$ is computable if there is a computable procedure that can compute rational approximations to $r$ to any desired degree of accuracy. For any natural number $k$, the algorithm will produce a rational number $q$ within $1/2^k$ of $r$. If one could enumerate the digits of $r$, then one could succeed in this task. And if one could succeed in this task, then one could produce digits, if one knew the status as to whether $r$ was rational or not. Namely, if $r$ was known to have a particular rational representation, then one could use this to produce the decimal digits; and if $r$ was known not to be rational, then with the approximations one could also enumerate the digits since one would know eventually what each digit must be.

The philosophical difficulty lies in the question of whether a computable real number is ultimately a particular real number or whether it is a program for producing the approximations or digits to such a number.

If we regard a computable real number as essentially a finite description of that number, provided by means of a program, then Turing's definition is inadequate, since addition and multiplication of real numbers will not be computable operations. I explain this in detail in my blog post. But if we regard computable real numbers as programs that produce arbitrarily precise rational approximations to a given real number, then all the ordinary functions we consider in real analysis, including addition, multiplication, exponentiation, trigonometric functions, logarithmic functions, and so on, will be computable. Clearly, this is the right way to do it.

Regarding infinite time Turing machines, these are concerned frankly with much larger ordinals than $\omega$, and their consequences and effects are realized only on much larger scales.

Answer 2

It sounds like you're asking whether the following are equivalent:

• $x$ is a computable infinite binary sequence in the usual sense, that is, the function $i\mapsto x(i)$ is computable.

• There is an ITTM $M$ such that $x$ is the output tape configuration of $M$ (on input $0$, say) at stage $\omega$.

(I'm shifting from reals to sequences to avoid tedium re: multiple expansions. I'm also going to think about machines with distinct input/output/work tapes, again purely for convenience.) This is definitely false: the latter is a much weaker condition than the former. In the language of the arithmetical hierarchy, the two notions correspond to $\Delta^0_1$ and $\Pi^0_2$ respectively. The latter is much broader. For example, the sequence whose $i$th bit is $1$ iff the $i$th Turing machine halts on all inputs is $\Pi^0_2$.

It may help to think of an intermediate notion, that of a limit computable sequence. It turns out that a sequence $x$ is limit computable iff it is Turing reducible to ${\bf 0'}$, iff it is $\Delta^0_2$, iff there is an ITTM $M$ such that $x$ is the output tape configuration of $M$ (on input $0$, say) at stage $\omega$ and each cell of the output tape has only changed value finitely many times by stage $\omega$ (think "limit rule" as opposed to "lim-sup rule"). The gap between limit computable and computable is basically due to the fact that, in the latter case, we know when our computation has reached its final answer on a given bit.

We can give an "ITTM-stage-$\omega$" characterization of classical computability, but it's a bit boring. An infinite binary sequence $x$ is computable in the usual sense iff there is an ITTM $M$ whose "work alphabet" includes a distinguished symbol $*$ such that $x$ is the output tape configuration of $M$ (on input $0$, say) at stage $\omega$ and for each $n$ there is some stage $<\omega$ by which the $n$th cell on the work tape has symbol $*$ and if the $n$th cell on the work tape has symbol $*$ at stage $k$ then the $n$th cell of the output tape doesn't change its value after stage $k$. Basically, the $*$ symbol tells us when the computation of a given bit has stabilized.