It is claimed in the Hamkins and Lewis founding article "Infinite time Turing machines" (proof of the gap existence theorem 3.4) that for $\omega$ steps of a computation of a machine performing a dovetailing on input $0$, $\omega$ steps are also performed in each of the simulated machines.

How does this simulation work precisely? I would really appreciate to see the details of such a trick!

Is it possible to generalise the technique to any clockable ordinal $\alpha > \omega$?

If so, I wonder what kind of processes we can add to the dovetailing (e.g., checking properties, taking some additional time) so that "same time" still holds. What could be the limitations of such processes?

Thanks for explanations in advance!


I'm glad to hear that you're reading my paper. This particular method of dovetailing infinitely many computations into one, however, is relatively standard in computability theoretic constructions, and doesn't have anything essentially to do with infinitary computability.

Let me explain it a little. The idea is that you want to simulate infinitely many programs $p_0, p_1, p_2,\ldots$ on some specified input. First, by using a pairing function, you may think of the one-dimensional linear tape as encoding a matrix of infinitely many linear tapes, one for each program, with some extra space to organize the whole simulation. In this way, you effectively reserve plenty of space specifically for each program. Next, you begin the simulation, by starting to perform a few steps of $p_0$, then a few more steps of $p_0$ plus a few steps of $p_1$, then a few more steps of $p_0$, of $p_1$ and then of $p_2$, then a few steps of $p_0, p_1, p_2$ and $p_3$, and so on. Proceeding in this way, after infinitely many ($\omega$ many) steps of computation, you've performed $\omega$ many simulated steps in each of the computations $p_i$. Although during the simulation, the earlier programs seem always a little bit ahead, everybody catches up in the limit.

The same idea works for any limit ordinal, because the universal computation that simulates all computations (on fixed input $0$, say) catches up at every limit ordinal.

The infinitary context does require, however, that one must take care with a few issues in order that one may iterate such simulations past $\omega$. For example, one should perform the simulated computations in such a way that the limit configuration of the simulated tape is simulated properly by the limit process of the simulation limit. That is, at a limit stage, the tape of the simulator is updated by the limsup rule, and it should be arranged that this is also correctly updating the simulated computations at this limit as well. Also, there should be an appropriate flag set at limits so that the machine can recognize that the scratch tapes may have accumulating garbage at limit stages and especially at limits-of-limits. But these issues are easy enough to handle.

  • $\begingroup$ Now, suppose I want to ensure that my simulation still takes $\beta$ steps for $\beta$ steps performed in each of the simulated machines but let's add constraints. Assume for example that I also need to check a property taking less than $\beta$ steps at each limit stage. Is it possible to find a way to contain this simulation in so few steps or to find a sufficiently large $\beta$? $\endgroup$ – Igor Mar 14 '15 at 17:54

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.