3
$\begingroup$

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)?

$\endgroup$
4
  • 3
    $\begingroup$ The decimal expansion of one-third is also infinitely long. $\endgroup$ May 27 at 23:27
  • $\begingroup$ This definition is also known to be slightly problematic for other reasons, see jdh.hamkins.org/alan-turing-on-computable-numbers $\endgroup$ May 28 at 0:47
  • $\begingroup$ @DavidRoberts: If one treated circle-free machines as ITTM's, would the problem mentioned by Hamkins go away? $\endgroup$ May 28 at 17:23
  • $\begingroup$ @ThomasBenjamin I don't know, sorry. Joel's answer is hopefully what you need. $\endgroup$ May 29 at 0:37
5
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ Thank you for your answer: both yours and Dr. Scheweber's answers were very helpful. I would, however, like you to answer the following question (because rightly or wrongly I believe the answer to this question would be helpful to me in getting an understanding of ITTM's: Can ITTM's be useful in computing in nonstandard models of $PA$ and how does Tenenbaum's Theorem relate to ITTM computation? $\endgroup$ Jun 2 at 21:04
  • $\begingroup$ Of course the nonstandard models of $PA$ in question will be countable. $\endgroup$ Jun 2 at 21:34
  • 1
    $\begingroup$ Yes, indeed, a nonstandard model of PA can be constructed by the Henkin construction---you just need a path through the tree that constructs a complete consistent Henkin theory. In fact, with merely an oracle for the halting problem one can do this. So ITTMs can certainly do it. This shows that Tennenbaum's theorem does not apply directly to ITTMs. $\endgroup$ Jun 3 at 7:37
  • $\begingroup$ Interesting. However, the '$+$' and '$\times$' for a countable nonstandard model of $PA$ are certainly computable by an ITTM even though they are not recursive functions according to Tennenbaum's Theorem, aren't they? If one assumes a nonstandard natural number can be coded by a real (can they?) then does Tennenbaum's Theorem hold for the set of such reals that code the nonstandard natural numbers of a given countable nonstandard model of $PA$? (I understand the desirability of having the "ordinary functions we consider in real analysis, including addition, multiplication..be computable.") $\endgroup$ Jun 3 at 20:51
  • 1
    $\begingroup$ @ThomasBenjamin Sort of. Any theory $T$ has a model computable from $T'$ (this is easy to show; less trivially, the (relativized) low basis theorem implies that we can even get a model low above $T$). ITTMs are extremely powerful so $PA$ - even $TA$ - has ITTM-computable nonstandard models (consider the expansion of each theory by adding a constant + axioms saying that that constant is greater than each standard natural). Conversely, up to isomorphism there are continuum many nonstandard models of any theory of arithmetic, so by a counting argument there are plenty of non-ITTM-computable ones. $\endgroup$ Jul 7 at 18:33
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you also for your very nice answer. A question regarding the "ITTM-stage-$\omega$ characterization of classical computability" : If the $n$th cell on the work tape does not stop changing after stage $k$ but stops changing at stage $\omega$, can it be said that one has left "classical computably"? $\endgroup$ Jun 2 at 21:19
  • $\begingroup$ *classical computability $\endgroup$ Jun 7 at 21:00
  • $\begingroup$ @ThomasBenjamin I wouldn't say so: figuring out what happens at stage $\omega$ in an ITTM calculation is only a $\Pi^0_2$ question. That is, the tape configuration of an ITTM at stage $\omega$ on input sequence $s$ is uniformly $\Pi^0_2$ relative to $s$. Turing-degree-wise this is only ${\bf 0''}$. As Joel said in the last paragraph of his answer, ITTMs really only enter the picture in a serious way at much larger ordinals. In particular, the tape configuration at stage $\beta<\omega_1^{CK}$ on input sequence $s$ is uniformly $\Pi^0_\beta$ relative to $s$ (and for many $\beta$s much better), $\endgroup$ Jun 7 at 21:20
  • $\begingroup$ and so in particular hyperarithmetic (which I think most people would still consider within the sphere of classical computability theory). And I wouldn't even start thinking about ITTMs at that point, either; at a glance, I wouldn't expect ITTMs to become particularly relevant until around the first $\Sigma_2$-admissible ordinal (which is gigantic), although I'm not an expert. $\endgroup$ Jun 7 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.