0
$\begingroup$

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, 0\rangle$ 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, 0\rangle$ 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$)?

$\endgroup$
  • $\begingroup$ To your first question: The authors have built that capability into their machine. That is, at limit stages, their machine is automatically placed into a special 'limit state'. It is easy to tell when you are at stage $\omega$ because $\omega$ is the first stage at which the machine enters this limit state. To your second question: looks like an error, I would ignore it. $\endgroup$ – realdonaldtrump Dec 22 '18 at 13:42
  • $\begingroup$ @realdonaldtrump: I know that these machines enter the limit stage automatically. But what I am asking is: when exactly does this happen? What are conditions required for the limit stage to occur? The machine just generates the output indefinitely, but what are those special conditions in the computation process that allow the program to suddenly enter the limit stage? $\endgroup$ – lyrically wicked Dec 22 '18 at 14:25
  • $\begingroup$ What is the special property of addition that lets you add one plus one plus $\ldots$ and suddenly reach infinity? When exactly does that happen? $\endgroup$ – realdonaldtrump Dec 22 '18 at 18:50
  • $\begingroup$ @lyricallywicked You have the right idea in your edit. These definitions seem correct. Specifically, for the link you gave in the question, I am relying on definitions give at the beginning of page-10,15 respectively. Just one thing though. You must assume that the machine $M_2$ begins from empty tape. (this is to ensure that oracles can't be used) $\endgroup$ – SSequence Dec 25 '18 at 2:28
  • $\begingroup$ @SSequence: when an ITTM starts the computation, the input tape contains only blank symbols. But when an ITTM is in the first limit stage (and afterwards), the input tape may contain some real number with infinitely many non-blank symbols, right? Regarding oracle machines — as far as I understand, they require an additional (fourth) tape so that an ITTM can print queries for the corresponding oracle on this tape? $\endgroup$ – lyrically wicked Dec 25 '18 at 6:30
4
$\begingroup$

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,s\mapsto 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))_{\sigma\in 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.

$\endgroup$
  • 1
    $\begingroup$ Out of curiosity, why the downvote? $\endgroup$ – Noah Schweber Dec 22 '18 at 21:23
  • $\begingroup$ OK I think I finally have got an idea about "lim sup" (it seems its opposite to what I was thinking) for finitely valued variables at least. Because everytime I think I am going to read an article related to this topic (till the point that I can understand), I just give up because I couldn't find any example related to lim,sup,inf etc. I have an easier time understanding these definitions through quantification (over suitably large ordinal) and there are three or four different types of behaviours that I can think of as being fairly intrinsic. Think I will ask a separate question. $\endgroup$ – SSequence Dec 23 '18 at 2:36
  • $\begingroup$ Also, it seems that the abstract description you gave is interesting. I wonder if this kind of description can be used to give interesting enough models similar to finitary case, but other than machines or programs. I am thinking something like lambda calc., queue machines, GoL etc. Anyway, that's kind of off-topic to this question so I will stop. $\endgroup$ – SSequence Dec 23 '18 at 2:41
  • $\begingroup$ I do have one small question .... when one writes something like $\sigma \in Ord$, is it fully formal terminology ...... or at least can it be made formal in standard set theory? For example, if we were to define the function for describing the value of a cell on the tape, could we write its domain as $Ord$?? [while being sure that any potential issues with it can be resolved formally] $\endgroup$ – SSequence Dec 23 '18 at 15:06
  • 1
    $\begingroup$ @SSequence Yup, this is exactly the same as how we usually reason about classes in ZF (etc.) - we don't directly, but specific examples (via fixed formulas) are easy to deal with. $\endgroup$ – Noah Schweber Dec 23 '18 at 19:04

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.