Csdrhrt

The paper “Infinite Time Turing Machines” contains the following information:

At each step of computation, the head reads the cell values which it overlies, reflects on its state, consults the program about what should be done in such a situation and then carries out the instructions: it writes a $0$ or $1$ on (any of) the tapes, moves left or right and switches to a new state accordingly. This procedure determines the configuration of the machine at stage $alpha + 1$, given the configuration at stage $alpha$, for any $alpha$. It remains to somehow take a limit of these computations in order to identify the configuration of the machine at stage $omega$ and, more generally, at limit ordinal stages in the supertask computation.

[...]

The ordinal $omega$ is also clockable, since a machine can be programmed, for example, to move the head always to the right, until a limit state is obtained, and then halt.

If a machine $M$ encodes some ordinal, then $M$ can operate as follows: given an input $N$, this machine converts $N$ to a pair of natural numbers, obtains the relation between these two numbers, writes the corresponding bit to the output tape, then generates the next number ($N+1$) and repeats the procedure. But what I don’t understand is how exactly can we determine whether $M$ reaches a limit stage? There is no upper bound for $N$. And if $omega$ is an abstract ordinal not bounded from above by some finite number, then how can we technically know that at some particular moment, a particular machine has $omega$ steps done and should be put into a limit state?

I have also read this article. It contains some descriptions, but for example, in the following description:

Here is brief look of how machine works:

1. We know $0=langle 0, 0rangle$ doesn't belong to $omega$, so we "hard-code" it into machine.

[...]

8. After $omega$ steps halt.

I don't understand why $0=langle 0, 0rangle$ doesn't belong to $omega$ and how exactly can a machine halt after $omega$ steps.

EDIT

My mistake was that I was trying to imagine an ITTM computation as a physically possible process, instead of a purely mathematical construction. But all I needed to know is that at any stage, for any cell $C_i$, there exists only one, mathematically predetermined value for a symbol that may appear on $C_i$ before the machine reads it! There are no special moments of computation when the LIMIT transition is required to occur, because limit stages are mere abstractions implying that a non-halting computation has reached its limit and all cells are ready. Is my understanding correct?

For example, let $R$ denote a particular representation of a real number that encodes the following wellorder: $$0 prec 2 prec 4 prec ldots prec 1 prec 3 prec 5 prec ldots$$

Let $M_1$ denote a standard (non-halting) Turing machine that generates $R$ on the output tape.

Consider an ITTM $M_2$ that is identical to $M_1$, but with the following addition: as soon as the machine enters the limit stage, it halts.

Question: can we assume that a real number $R$ encoding the ordinal $omega + omega$ is the final output of $M_2$ (so the ordinal $omega + omega$ is writable by $M_2$), but $M_2$ will halt at time $omega$ (and clock the ordinal $omega$)?

What are conditions required for the limit stage to occur?

Well, it occurs exactly when ... we're at a limit stage.

First, let's remember how classical Turing machines work for the moment.

Time, for a usual Turing machine, is $omega$. The definition of Turing machine tells us how to take a machine $Phi$ (I'm ignoring oracles for now, but they don't substantively change the picture), an input $n$, and a finite ordinal $s$, and get a description (I've also heard this called the (complete) configuration) $D(n,s)$ of what's going on at time $s$ in the computation of $Phi(n)$. This consists of:

• What's written on the tape




• Where the head of the machine is




• What state the machine is in

at time $s$.

Note that in fact if we understand the map $n,smapsto D(n,s)$, we in fact understand the whole machine. So we can think of a Turing machine as exactly the sort of map described above, with the requirement that it have a certain form.

In an ITTM we do the same thing, but now $s$ is allowed to be an arbitrary ordinal. This should be unsurprising given the name "Infinite Time Turing Machine."

Ignoring details for a moment, you can think of an ITTM as a map taking an input $A$ and an ordinal $sigma$ to a description $D(A,sigma)$ ... following some rules. The rule for successor steps - that is, the rule determining $D(A,alpha+1)$ given $D(A,alpha)$ - is the same as for classical Turing machines, but now we need a new rule to figure out what $D(A,omega)$ should be (or $D(A,lambda)$ for any limit ordinal $lambda$, more generally). Note that everything seems to be a problem here:

• Where should the head of the machine be on the tape?




• What state should the machine be in?




• Given a cell on the tape, what symbol should be in that cell (noting that it might have changed back and forth infinitely often leading up to the limit stage)?

Now let's be a bit concrete. Given an input $A$, an ITTM produces a run on input $A$: this consists of an ordinal-indexed sequence of descriptions, namely $$(D(A,sigma))_{sigmain Ord}.$$ For example, let's ignore the halting state for the moment and consider a machine with a single state, which is simultaneously the start state and the limit state, and which flips whatever bit it's looking at and then moves to the right.

Starting it on an all-zeroes tape, here's the run we get (using red to denote the symbol currently being looked at; note that since there's only one state, we can safely ignore mentioning it for simplicity).

• Time $0$: $(color{red}{0}, 0,0,0,0,0,0,...)$




• Time $1$: $(1, color{red}{0}, 0,0,0,0,0,...)$




• Time $2$: $(1,1,color{red}{0}, 0,0,0,0,...)$




• Time $3$: $(1,1,1,color{red}{0}, 0,0,0,...)$




• ...




• Time $omega$: $(color{red}{1}, 1,1,1,1,1,1,...)$




• Time $omega+1$: $(0,color{red}{1}, 1,1,1,1,1,...)$




• Time $omega+2$: $(0,0,color{red}{1}, 1,1,1,1,...)$




• ...




• Time $omega^2$: $(color{red}{1}, 1,1,1,1,1,1,...)$




• Time $omega^2+1$: $(0,color{red}{1},1,1,1,1,1,...)$




• ...

I've explicitly listed two different limit stages: $omega$ and $omega^2$. Stage $omega$ was simple, since each cell on the tape had an "eventual value" (namely $1$); stage $omega^2$ was a bit more interesting, since each cell alternated between $0$ and $1$ cofinally often, and so we had to use the limit rule for symbols on the tape as well (namely, we use the limsup of the symbols). Note that at each limit stage the head "retreats" to the initial cell in the tape.

The relevant text in the Hamkins/Lewis article is (emph. mine):

To set up such a limit ordinal configuration, the head is plucked from wherever it might have been racing towards, and placed on top of the first cell. And it is placed in a special distinguished limit state. Now we need to take a limit of the cell values on the tape. And we will
do this cell by cell according to the following rule: if the values appearing in a cell have converged, that is, if they are either eventually 0 or eventually 1 before the limit stage, then the cell retains the limiting value at the limit stage. Otherwise, in the case that the cell values have alternated from 0 to 1 and back again unboundedly often, we make the limit cell value 1. This is equivalent to making the limit cell value the lim sup of the cell values before the limit.

Now let's go a bit more complicated, and see how to clock $omega$. Here I do need a "halt" state.

Our machine will have two states, $S_0$ and $S_1$:

• $S_0$ is the start state; it transitions only to itself, moves to the right, and doesn't change what's on the tape.




• $S_1$ is both the limit state and the halting state.

Now here's the run we get (starting with all-$0$s on the tape) - note that this time we do need to keep track of what state the machine is in:

• Time $0$: state = $S_0$, tape = $(color{red}{0}, 0,0,0,0,0,0,...)$




• Time $1$: state = $S_0$, tape = $(0, color{red}{0}, 0,0,0,0,0,...)$




• Time $2$: state = $S_0$, tape = $(0,0,color{red}{0}, 0,0,0,0,...)$




• Time $3$: state = $S_0$, tape = $(0,0,0,color{red}{0}, 0,0,0,...)$




• ...




• Time $omega$: state = $S_1$, tape = $(color{red}{0}, 0,0,0,0,0,0,...)$.

Note that we've leapt as by magic to $S_1$ - simply because $S_1$ was the designated limit state! And now, at time $omega$, we're in the halt state, and so we halt.