FANDOM

10,835 Pages

This is just a short blog post in which I'll describe how to, consistently, construct fundamental sequences for ordinals far beyond $$\omega^\text{CK}_1$$.

This method makes use of Hamkins' infinite time Turing machines. To make everything unambiguous, here are all technicalities connected with machines themselves, and here is a way of representing ordinals as binary strings.

Up to $$\lambda$$

$$\lambda$$ is my favorite greek letter and smallest ITTM ordinal at the same time, so we will start with it.Here is the definition:

Let $$\alpha$$ be a limit ordinal such that $$\omega<\alpha\leq\lambda$$. Then we define $$\alpha[n]$$ to be the largest ordinal smaller than $$\alpha$$ writable by some $$n$$-state ITTM, or $$0$$ if no $$n$$-state machine writes an ordinal.

Why does this definition work? We know that writable ordinals don't have gaps (if you haven't seen a proof, try it yourself! It's not too hard) and $$\lambda$$ is, by definition, supremum of all writable ordinals, then all infinite ordinals below $$\alpha$$ are writable. But, as $$\alpha$$ is limit, and there is only finitely many $$n$$-state ITTMs, only finitely many of these ordinals are candidates for $$\alpha[n]$$. But we nevertheless can write unbounded in $$\alpha$$ number of ordinals, so we indeed get a fundamental sequence for $$\alpha$$.

Up to $$\gamma$$?

One could think that analoguous definitions for ordinals below $$\gamma$$ would be possible:

Let $$\alpha$$ be a limit ordinal such that $$\omega<\alpha\leq\gamma$$. Then we define $$\alpha[n]$$ to be the largest ordinal smaller than $$\alpha$$ clockable by some $$n$$-state ITTM, or $$0$$ if no $$n$$-state machine writes an ordinal.

The problem is: clockable ordinals have gaps. First gap starts at $$\omega^\text{CK}_1$$ and then $$\omega^\text{CK}_1+\omega$$ is clockable. So, even if we limit ourselves to clockable $$\alpha$$, this won't work. For example, every sequence unbounded in $$\omega^\text{CK}_1+\omega$$ would have elements of form $$\omega^\text{CK}_1+k$$ for $$k$$ finite. But no such ordinal is clockable. So this won't work.

Fortunatelly, $$\gamma=\lambda$$, so we don't have to worry.

Up to $$\zeta$$

Let $$\alpha$$ be a limit ordinal such that $$\omega<\alpha\leq\zeta$$. Then we define $$\alpha[n]$$ to be the largest ordinal smaller than $$\alpha$$ eventually writable by some $$n$$-state ITTM, or $$0$$ if no $$n$$-state machine writes an ordinal.

Does this work? Yes it does! Eventually writable ordinals also don't have gaps (argument similar to one for writable ones, but a bit more tricky!), so reasoning just like in case of $$\alpha\leq\lambda$$.

Up to $$\Sigma$$?

Let $$\alpha$$ be a limit ordinal such that $$\omega<\alpha\leq\Sigma$$. Then we define $$\alpha[n]$$ to be the largest ordinal smaller than $$\alpha$$ accidentally writable by some $$n$$-state ITTM, or $$0$$ if no $$n$$-state machine writes an ordinal.

Does this work? Yes it doesn't. Wait, what

Accidentally writable ordinals don't have gaps either (argument just like for eventually writable), true, but there is a major difficulty: for some $$n$$, we get infinitely many ordinals accidentally writable by machines with $$n$$ states. Simple example is a machine writing $$\omega+k$$, erasing it, writing $$\omega+k+1$$ and looping like that. One could replace "largest ordinal" by "upper bound of blah blah", but this won't solve above problem, as we'd have $$\omega2[n]=\omega2$$, which is nonsense. However, I have an idea on how to fix this.

First of all, let's define the level of a machine (ideas for a more catchy names are welcomed) to be an upper bound of all ordinals this machine accidentally writes, and $$0$$ if it writes none. Note that this ordinal is smaller than or equal to $$\Sigma$$. Now here is my definition of fundamental sequences:

Let $$\alpha$$ be a limit ordinal such that $$\omega<\alpha\leq\Sigma$$. Then we define $$\alpha[n]$$ to be the largest ordinal smaller than $$\alpha$$ which is the level of some $$n$$-state ITTM.

Does this work? I don't know. Equivalent condition for this to be a well-defined is statement that every infinite ordinal up to and including $$\Sigma$$ is a level of some machine. The basic idea for proof of equivalence is that if $$\alpha+\omega$$ has such fundamental sequence, then some $$\alpha+k$$ is a level, and then we apply technique similar to Hamkins' and Lewis' speed-up theorem to show that $$\alpha$$ is a level too. In other direction it's trivial.

Let's call an ordinal $$\alpha$$ achieveable if there is a machine which accidentally writes $$\alpha$$ but no larger ordinal. Note that every achievable ordinal is a level, and every level which is a successor is achievable. However, $$\Sigma$$ is an example of a level which is not achievable.

I state the following conjecture: let $$\tau$$ be the smallest ordinal which isn't a level of any machine. Then $$\zeta<\tau<\Sigma$$. Note that well-foundedness of my definition is equivalent to $$\tau=\Sigma+1$$. I know that $$\tau$$ is either a limit ordinal or a successor of a limit ordinal. My conjecture says that every eventually writable ordinal, along with $$\zeta$$, is a level, but some accidentally writable ordinal isn't. Note that every writable ordinal and $$\lambda$$ is a level.

I'll state this, I guess really risky, conjecture too: $$\tau=\zeta+1$$

Also, note that my definition of fundamental sequences will work for all numbers below $$\tau$$, and it won't work for smallest limit ordinal above $$\tau$$.

NEWS: a theorem: every achievable ordinal is eventually writable. Proof: Let $$\alpha$$ be achievable by machine M. We will construct a machine which eventually writes $$\alpha$$. Let our new machine simulate M on scratch tape only. After every step we look at M's output tape. If it is an ordinal, we copy it to our real output tape. If, however, there is already an ordinal on the tape, we compare it and overwrite it only if we are about to write larger ordinal. At limit stages output tape can become a mess, so we clear it in that case. As $$\alpha$$ is largest ordinal accidentally writable by M, it will be eventually written on a tape never to be overwritten.

Corollary: $$\zeta+1$$ is not achievable, thus, as it's successor, it's not a level. So $$\tau\leq\zeta+1$$

For the moment I thought I have a proof that $$\tau\geq\zeta$$, but it turned out to be incorrect. It might be possible to fix the proof, though.

I was able to prove that levels are unbounded in $$\zeta$$: let's take any eventually writable ordinal $$\alpha$$. We will show that there is a level greater than or equal to $$\alpha$$. Let machine M eventually write $$\alpha$$. One of known results (I believe it's due to P.D.Welch) is that eventually writable ordinals are exactly these appearing before $$\zeta$$-th step of computation. So we know $$\alpha$$ will appear on M's output before $$\zeta$$, never to be changed. So level of M is at least $$\alpha$$. But some larger ordinal might have been accidentally written before output stabilized. If that happened, it still happened before $$\zeta$$, so these were all eventually writable ordinals. Another result (not exactly, but easy corollary of one) is that all eventually writable ordinals can't appear uniformly below $$\zeta$$. Indeed, no sequence unbounded in $$\zeta$$ can appear uniformly below $$\zeta$$. As ordinals accidentally writable by M are time-bounded by $$\alpha<\zeta$$, they can't limit to $$\zeta$$. So level of M is eventually writable and greater than or equal to $$\alpha$$.

If one proves similar theorem for achieveables, we will almost have proof that every eventually writable is a level.