0
$\begingroup$

In the paper "Infinite Time Turing Machines", the following information is given:

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 (pp. 569).

Moreover, the authors make use of a technique in which we can detect whether the machine has entered the limit state infinitely many times, i.e., whether the machine has run for $ω^2$ steps. The basic idea is to use a cell as a "flag" such that, once every limit stage, the machine writes a 1 to the cell and then immediately writes a 0 to the same cell (the cell's initial value is 0). Using this technique, once we hit $ω^2$ steps, the value of the flag cell will be a 1 in the limit state of the machine for the first time.

My question is this: Can this flag cell ever again be a 0 at any future limit state? It seems like it cannot be. If we write a 0 to that cell, then the next time the machine enters the limit state (at $ω^2 + ω$ steps), the cell value will be updated to 1. And this will be true at every future limit state. Is this reasoning correct? If it isn't correct, then I'm struggling to see how the flag cell technique could work. On the other hand, if it is correct, then I'm struggling to see how the following from the above mentioned paper works (this is part of the proof of Theorem 2.2):

There is a slight complication at the compound limits (limits of limits) since at such stages we will have a lot of garbage on the scratch tape, but because we were gradually erasing elements from the field of the relation coded by the real on the input tape, the input tape has stabilized to the intersection of those relations, which is exactly what we want there. By flashing a flag on and then off again every time we reach a limit stage, we can recognize a compound limit as a limit stage in which this flag is on, and then in $ω$ many steps wipe the scratch tape clean before continuing with the algorithm (ibid., pp. 572, emphasis added).

I don't understand how we can "wipe the scratch tape clean" given that some of the cells on the scratch tape could have flipped from 0 to 1 and back again unboundedly often. For if there are cells like this, then as soon as we finish wiping the scratch tape clean in $ω$ steps, the machine will enter the limit state and all of those cells will be flipped back to 1, resulting in a scratch tape that is no longer "clean." Is this correct? I'm very confused about this.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I'll use the notation "$n[\alpha]=i$" for "cell $n$ at stage $\alpha$ contains $i$." Also, I'll start indexing both cells and stages at $0$.

No, your understanding is incorrect: at stage $\omega^2+\omega$, the "coding cell" will contain a $0$, not a $1$.

The idea is the following. For simplicity, suppose our "coding cell" is the leftmost cell. Here's what things look like from that cell's perspective:

  • For each finite $n$ we have $0[n]=0$.

  • We then begin stage $\omega$. Looking backwards from $\omega$, the behavior of cell $0$ has been completely constant, so we get $0[\omega]=0$. Our limit state strategy kicks in, so we set $0[\omega+1]=1$ and $0[\omega+2]=0$. Indeed, $0[\omega+n]=0$ for all finite $n>1$.

  • We then hit stage $\omega\cdot 2$. Looking backwards from $\omega\cdot 2$, the behavior of cell $0$ has not been completely constant, but it has been eventually constant which is what matters here: we get $0[\omega\cdot 2]=0$. Again, our limit state strategy kicks in and we set $0[\omega\cdot 2+1]=1$ and $\omega\cdot 2+n]=0$ for all finite $n>1$.

  • More generally, for each finite $k,n$, we have $0[\omega\cdot k+n]=0$ exactly unless $k>0$ and $n=2$.

  • OK, now what happens at stage $\omega^2$? Well, at this point when we look back at history the behavior of cell $0$ is no longer even eventually constant, so $0[\omega^2]=1$. Our limit state strategy sees this, and realizes that we've just entered a limit-of-limits step, so [PRESUMABLY STUFF HAPPENS].

  • But then we reset things: $0[\omega^2+n]=0$ for all finite $n>1$ again. This means that looking backwards at stage $\omega^2+\omega$, the content of cell zero eventually stablized to $0$, and so $0[\omega^2+\omega]=0$.

$\endgroup$
5
  • $\begingroup$ Thank you for your answer! I think, however, that I'm still having some conceptual difficulties that I'm having trouble formulating at the moment. One follow-up I would have is this: Suppose that after $ω^2 + ω$, the "coding cell" is never written to again. Will it remain 0 forever? Or would it change to a 1 at $ω^2 + ω^2$, for instance? Does "wiping" the tape in $ω$ steps effectively erase the history of every cell on the tape with respect to limit state updating? $\endgroup$
    – Kyle S
    Apr 4 at 19:53
  • $\begingroup$ @KyleS I'm not sure I understand the question but the point of the "limit behavior" is that at a limit stage $\lambda$, cell $n$ contains a $1$ iff for the set $\{\alpha<\lambda: n[\alpha]=1\}$ is unbounded in $\lambda$ specifically. This means that "only the tail behavior matters" - for example, if cell $5$ (to avoid confusion) contains a $1$ on every stage until $\omega^2+\omega+7$ and then contains a $0$ from stage $\omega^2+\omega+8$ to $\omega^2+\omega^2$, at stage $\omega^2+\omega^2$ cell $5$ will be set to zero. There have been lots of $1$s in cell $5$'s past, but not recently. $\endgroup$
    – Noah Schweber
    Apr 4 at 20:19
  • $\begingroup$ Maybe it's the concept of the "tail behavior" that I'm struggling with. Because, for instance, with the example in your original answer, at $ω^2 + ω$, my intuition is that if we look at the entire history of the code cell, it flipped from 0 to 1 and back to 0 again infinitely many times, so the value of the cell at $ω^2 + ω$ should be 1. But it's not actually because it's only the tail behavior that determines the limit. Could you please explain the intuition behind the concept of being "unbounded in $\lambda$ specifically?" I think that's perhaps what I'm struggling with. $\endgroup$
    – Kyle S
    Apr 4 at 20:42
  • $\begingroup$ @KyleS Ah, now I see the issue! "Infinitely often" is totally irrelevant. The only question that matters at a limit stage $\lambda$ for cell $n$ is whether the set $$\{\beta<\lambda: n[\beta]=1\}$$ is unbounded in $\lambda$ - that is, whether $$\forall \alpha<\lambda\exists \beta<\lambda(\alpha<\beta\wedge n[\beta]=1).$$ For example, the set of finite ordinals is infinite but not unbounded in $\omega^2$ (or even in $\omega\cdot 2$). $\endgroup$
    – Noah Schweber
    Apr 4 at 23:55
  • $\begingroup$ Oh, okay! I think I am finally understanding. This makes sense. I was conflating "infinitely often" and "unboundedly often." Thank you so much! $\endgroup$
    – Kyle S
    Apr 5 at 13:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .