FANDOM


I got so much into these ITTM levels and \(\tau\) ordinal I defined that I decided to create whole separate blog post for them, partially because blog post linked above doesn't really fit that purpose.

Definitions

I assume familiarity with infinite time Turing machines and all related topics, like accidentally writable ordinals.

Let's call an ordinal \(\alpha\) a level if there exists an ITTM M such that \(\alpha\) is an upper bound of all ordinals accidentally written by M when ran on empty input.

Let's call an ordinal \(\alpha\) achievable if there exists an ITTM M such that \(\alpha\) is accidentally written by M when ran on empty input, but no larger ordinal is.

Define \(\tau\) to be the smallest ordinal which isn't a level of any ITTM.

Simple facts

I might use these facts without even mentioning the use of them.

Fact 1: Every achievable ordinal is a level.

Assume \(\alpha\) is achievable by machine M. Then \(\alpha\) is the largest element of the set of ordinals accidentally written by M. If a set has the largest element, then it's its upper bound, so \(\alpha\) is level of M.

Fact 2: If ordinal is a level and is a successor, then it's achievable.

Let \(\alpha+1\) be a non-achievable successor level. It's level of some machine M. By argument similar to one used above, \(\alpha+1\) cannot be the greatest accidentally writable ordinal of M, as it'd be achievable. So M accidentally writes only ordinals which are \(\leq\alpha\). Thus the upper bound of these ordinals would be at most \(\alpha\), so level of M couldn't be \(\alpha\), a contradiction.

Fact 3: \(\Sigma\) is a non-achievable level.

Let's take universal machine U which, on scratch tape, simulates operation of all ITTMs, and writes down on output tape, successively, every accidentally writable real. Among these will be all accidentally writable ordinals, so their upper bound will be \(\Sigma\). So level of U is \(\Sigma\). On the other hand, if \(\Sigma\) was achievable, it'd be accidentally writable, which it isn't.

Fact 4: No ordinal larger than \(\Sigma\) is a level. In particular, \(\tau\leq\Sigma+1\).

Upper bound of all accidentally writable ordinals is \(\Sigma\), so an upper bound of any subset of these is at most \(\Sigma\). As levels are such upper bounds, first part of claim follows. Thus we have \(\Sigma+1\) is not a level. So the least non-level, \(\tau\), is at most \(\Sigma+1\).

Lemmata

Lemmata in here are indirectly connected to \(\tau\), levels and/or achievable ordinals.

Lemma 1: Eventually writable ordinals are closed under addition and multiplication.

To prove the lemma is to show that if \(\alpha,\beta\) are eventually writable, then so are \(\alpha+\beta,\alpha\beta\). First, addition. We construct machine P which will simulate machines M and N eventually writing \(\alpha\) and \(\beta\) respectively in parallel. At every step of both machines we check if their outputs are both ordinals. If so, we write on output a follwing ordering: we have numbers \(a_k\) ordered using ordinal written by M, and \(b_k\) ordered using ordinal written by N, plus we have \(a_k\prec b_l\) for all \(k,l\). If output of M or N changes, we erase output of P and repeat this process. Eventually outputs of M and N will stabilize, and so will output of P. It's easy to see P is eventually writing \(\alpha+\beta\).
For multiplication, we will create \(\beta\) "blocks" of ordinals, each with \(\alpha\) ordinals, ordered lexicographically. More formally, we will have \(a_{0,k}\) ordered by \(\alpha\), same with \(a_{1,k}\) and so on, where first number in subscript goes through all ordinals below \(\beta\). We also give \(a_{\gamma,k}\prec a_{\delta,l}\) if \(\gamma<\delta\), so we order these blocks using \(\beta\). We apply this similarly to addition, resulting in machine Q eventually writing \(\alpha\beta\).

Lemma 2: \(\zeta^{0^\triangledown}=\zeta\) (here \(\triangledown\) is a lightface jump operator for ITTM)

Note that \(0^\triangledown\) is eventually writable (we can make machine U which marks which machines have halted. At stage \(\gamma\) they will all halt, and output will stabilize). Assume real \(r\) is eventually written from \(0^\triangledown\) by the machine M. We construct non-oracle machine N which in parallel simulates U and M. M, instead of full oracle, uses the output of U. When output of U changes, we restart simulation of M and let it use modified output of U. Eventually, U will write down \(0^\triangledown\), so M will be able to operate as if it had access to full oracle. So N will eventually write \(r\). It follows that \(\zeta^{0^\triangledown}\leq\zeta\), and of course \(\zeta^{0^\triangledown}\geq\zeta\) and result follows.

Lemma 3: Let output of machine M eventually stabilize. Then it stabilizes at stage which is less than \(\zeta\).

The proof of this fact uses Main Proposition of P. D. Welch. From it follows that every non-halting machine repeats its configuration from stage \(\zeta\) at stage \(\Sigma\). Hence, if the output of the machine changes between these two stages, it will change infinitely many times. So, if output of M stabilizes, it stabilizes before \(\Sigma\). Now we can modify a proof of Main Proposition to eventually write a stage at which whole output stabilizes (not only one cell), thereby proving this lemma.

Lemma 4: \(\zeta\), nor any larger ordinal, can be accidentally written at stage less than \(\zeta\).

Assume not - let machine M accidentally write \(\zeta\) at stage \(\alpha<\zeta\). Then \(\alpha\) is eventually writable by some machine N. Construct machine P which looks at ordinals written by N, and it simulates M up to a point specified by this ordinal and returns content of its output. Eventually, N will stabilize with \(\alpha\) on tape, and P will simulate \(\alpha\) steps of M and stabilize with its output. But by assumption this would mean \(\zeta\) is eventually writable, a contradiction. Same goes for every larger ordinal.

Lemma 5: Let \(\triangledown^\alpha\) be \(\triangledown\) operator trasfinitely iterated up to \(\alpha\), for \(\alpha\) eventually writable. Then computational strength of \(\triangledown^\alpha\) doesn't depend on representation of \(\alpha\), and for every \(\alpha\) this is eventually computable. Indeed, we can set up an eventual computation so that if output of a machine is always either \(\triangledown^\alpha\), or is strictly weaker than it.

First two claims are proved in this paper. For third claim we will show it for a construction in that paper. This goes by transfinite induction - as in theorems 12 and 13 below, computation of \(0^\triangledown\) is either finished, or is computable up to some point, so it works for \(\alpha=1\). We just have to note that the same exactly works for \(\alpha\) being successor. For limit, \(\alpha\) we either have results for all ordinals below \(\alpha\) already correctly computed, and from it we can compute correct \(0^{\triangledown^\alpha}\), or some \(\beta<\alpha\) isn't ready. By induction, we have that result for \(\beta\) is computable from some lower ordinal \(\delta<\beta\), from which it follows that partial result of whole computation is computable from \(0^{\triangledown^\delta}\), which we actually wanted to prove.

Lemma 6: Ordinals of form \(\lambda^{0^{\triangledown^\alpha}}\) for \(\alpha<\zeta\) are unbounded in \(\zeta\)

Three proofs, two short, one not: 1. It's quite clear that \(\alpha\) is computable from \(0^{\triangledown^\alpha}\), so \(\lambda^{0^{\triangledown^\alpha}}>\alpha\). 2. There is \(\zeta\) ordinals in question, no two of which are equal, and each smaller than \(\zeta\), so they must be cofinal with \(\zeta\), result follows. 3. Assume \(\alpha\) is not computable from any of \(0^{\triangledown^\beta}\). It must be then that \(\alpha\) can contribute as a new eventually decidable degree. But hierarchy \(0^{\triangledown^\beta}\) contains all eventually writable degrees (link), contradiction.

Theorems

Theorem 1: Every writable ordinal is achievable.

Let machine M write \(\alpha\). We construct machine M' in the following way: first it simulates M on scratch tape, which will eventually halt and give us \(\alpha\). We then copy \(\alpha\) onto output tape of M'. As M' accidentally writes only \(\alpha\), this ordinal is achieved by M'.

Theorem 2: \(\lambda\) is a level. It is also achievable.

We will first prove that \(\lambda\) is a level. Take machine U which simulates all ITTMs, but this time it will only write on output ordinals which appear on output of halting machines. Every writable ordinal will be written at one point, and every ordinal accidentally written will be writable, so their upper bound is \(\lambda\). Thus \(\lambda\) is the level of U.
To show it's achievable, we will construct a machine which eventually writes the sum of all writable ordinals, which is easily seen to be \(\lambda\). Fix some ordering \(T\) of ITTMs. We will construct an ordering in a following way: \(n_0\prec n_1\prec ...\prec n_k\prec ...\) will form an initial segment of length \(\omega\). This will correspond to \(T\)-indexes all the machines which haven't halted (yet). After that, we will have numbers \(a_{1,1},a_{1,2},a_{1,3},...,a_{1,k},...\), which within themselves will be ordered using the writable ordinal which was written by \(T\)-least machine which already halted. Then we will have \(a_{2,k}\) ordered similarly using second \(T\)-least machine, and so on. We also will have \(n_k\prec a_{p,q}\) for all \(k,p,q\) and \(a_{k,m}\prec a_{l,n}\) for \(k<l\). One can easily verify this is ordering we are looking for and that it's eventually writable. Also, we will have at no point written a larger ordinal, as any sum of writable ordinals can't exceed sum of all of them.

Theorem 3: Eventually writable achievable ordinals are closed under addition and multiplication.

We can use lemma 3 using following observation: if machines M and N write no ordinals larger than \(\alpha,\beta\), then machines P and Q won't write any ordinal larger than \(\alpha+\beta,\alpha\beta\). So, if \(\alpha,\beta\) are achievable by M and N, then \(\alpha+\beta,\alpha\beta\) are achievable by P and Q.

Corollary 1: \(\tau\geq\lambda^\omega\)

Using theorems 1 and 2 we see that every ordinal \(\leq\lambda\) is achievable. They are also eventually writable. Because every ordinal below \(\lambda^\omega\) is expressible using numbers up to \(\lambda\) and addition and multiplication, we can apply theorem 3 to show that every ordinal up to \(\lambda^\omega\) is achievable and thus level. So least non-level is at least \(\lambda^\omega\).

I'm sure above result can be extended much, much further, but it's quite difficult to ensure machines won't write anything larger than expected result.

Theorem 4: If \(\alpha+1\) is achievable, then so is \(\alpha\).

Let machine M achieve \(\alpha+1\). We construct M' which simulates M and, for every ordinal written by M, it checks if it's successor ordinal. If it is, then we remove it's largest element, thus decreasing ordinal by 1. Because M writes \(\alpha+1\), M' will write \(\alpha\), and as M writes nothing above \(\alpha+1\), M' will write nothing greater than \(\alpha\). Thus \(\alpha\) is achievable by M'.

Theorem 5: If \(\alpha\) is achievable, then so is \(\alpha+1\).

Let machine M achieve \(\alpha\). Machine M' will simulate M and for every ordinal M writes it will add a new largest ordinal to it, thus increasing it by 1. By reasoning similar to theorem 4, M' achieves \(\alpha+1\).

Corollary 2: \(\tau\) is either a limit ordinal, or a successor of such.

Assume not, let \(\tau=\alpha+2\) for some \(\alpha\). As \(\tau\) is smallest non-limit, \(\alpha+1\) is a limit, and thus it's achievable. By theorem 5 \(\alpha+1+1=\tau\) is then also achievable, which contradicts definition of \(\tau\).

Theorem 6: Every achievable ordinal is eventually writable.

Let's assume M achieves \(\alpha\). Machine N will simulate M and will keep track of the largest ordinal M has written up to some point. We will store this ordinal on N's output tape. If M writes some new ordinal, we compare it with one stored by N. If the former is larger, we overwrite N's output with it. After infinitely many changes, we might get in result some mess, but then we just overwrite it with next ordinal M writes. Because \(\alpha\) is the largest ordinal written by M, N's output will eventually stabilize with \(\alpha\). Thus \(\alpha\) is eventually writable.

Corollary 3: \(\tau\leq\zeta+1\)

\(\zeta+1\) is not eventually writable, thus it's not achievable. As it's a successor, it's not a limit. So, as in fact 4, we get our bound on \(\tau\).

Theorem 7: \(\tau\) is either the first non-achievable ordinal or successor of it.

Let \(\alpha\) be the least non-achievable. Every ordinal below \(\alpha\) is achievable and thus a level. We also have that \(\alpha+1\) is not achievable (or we could derive contradiction from theorem 4) and thus not a level. So either \(\alpha\) isn't a limit, in which case \(\alpha=\tau\), or \(\alpha\) is a level, in which case \(\alpha+1=\tau\).

Theorem 8: "\(\alpha\) is achievable by machine M" is \(0^\triangledown\)-decidable. Thus "\(\alpha\) is achievable" is \(0^\triangledown\)-decidable.

Note that with \(0^\triangledown\) we can obviously solve halting problem. Let machine P simulate M and check if \(\alpha\) is ever written. P will halt iff it's the case. Then let machine Q simulate M and check if it writes any ordinal larger than \(\alpha\) is written. Q will halt iff it's the case. Now give machine N access to \(0^\triangledown\) and ask it if P halts and Q doesn't. If it happens, this exactly means that \(\alpha\) is achievable by machine M. So N decides this question. Second claim follows if machine N asks similar query about every ITTM.

Theorem 9: \(\tau\) is \(0^\triangledown\)-writable.

We will prove that the least non-achievable ordinal \(\alpha\) is \(0^\triangledown\)-writable. Run the universal machine U used in fact 3, and for every ordinal it writes, check if it is achievable. Eventually, as there are non-achievable accidentally writable ordinals (e.g. \(\zeta+1\)) we will hit an ordinal greater than, or equal to, \(\alpha\). As writable ordinals have no gaps, and by relativisation, neither do \(0^\triangledown\)-writable ordinals, we get that \(\alpha\) is \(0^\triangledown\)-writable too. From it and theorem 7 we clearly see that \(\tau\) is \(0^\triangledown\)-writable as well.

Corollary 4: \(\tau<\zeta\)

As \(\tau\) is \(0^\triangledown\)-writable, we get \(\tau<\lambda^{0^\triangledown}\), and, by relativisation of \(\lambda<\zeta\) and lemma 2, we have \(\lambda^{0^\triangledown}<\zeta^{0^\triangledown}=\zeta\). Result follows.

So we have finally shown that there are eventually writable non-limits, which disproves my conjecture of \(\tau=\zeta+1\). Showing \(\tau<\lambda^{0^\triangledown}\) is actually incredibely better result, because there is a whole hierarchy of \(\zeta\) different oracle levels between \(\lambda\) and \(\zeta\), but I don't doubt \(\tau<\zeta\) is a lot easier to understand.

Turns out my argument for theorem 8 is incorrect - I assumed that given ordinal \(\alpha\) and \(0^\triangledown\) we can say things about non-oracle machines allowed to look at \(\alpha\), but that actually is exactly the difference between \(0^\triangledown\) and \(0^\blacktriangledown\) - the former one is allowed to only look at machines starting at empty input. Mystery solved.

Theorem 10: If \(\zeta\) is not a level, then levels are unbounded in \(\zeta\).

Take any ordinal \(\alpha<\zeta\). Let M eventually write \(\alpha+1\). It's obvious that level of M is greater than \(\alpha\). By lemma 3, output of M will stabilize strictly before \(\zeta\), thus, by lemma 4, M will not accidentally write \(\zeta\) nor any greater ordinal. So set of ordinals accidentally written by M is subset of \(\zeta\), so its level is at most \(\zeta\). From theorem assumption, \(\zeta\) is not a level, so level of M is between \(\alpha\) and \(\zeta\). Because \(\alpha\) was arbitrary, it follows levels are unbounded in \(\zeta\).

Earlier I claimed I have proved the above fact without assumption that \(\zeta\) is not a level. However I haven't found required reference, thus I cannot really prove that.

Conjecture 1: Levels are unbounded in \(\zeta\).

Question 1:  Is \(\zeta\) a level?

Note that from theorem 6 follows that \(\zeta\) is not achievable, so the only possibility for that to be true is that there exists a machine M writing an unbounded set of eventually writable ordinals. I doubt this possibility, as I don't think there is any way of determining if a given ordinal is eventually writable.

Next theorem is the extension of theorem 3:

Theorem 11: Let \(F\) be a nondecreasing function from ordinals to ordinals which is ITTM-computable. If \(\alpha\) is achievable, then so is \(F(\alpha)\).

Let \(\alpha\) be achievable by machine M. Let machine N do the following: it simulates M and for every ordinal \(\beta\) M accidentally writes, N computes \(F(\beta)\) and writes it on output. Because \(\alpha\) is accidentally written by M, N accidentally writes \(F(\alpha)\). Because M writes no ordinal above \(\alpha\) and \(F\) is nondecreasing, N writes no ordinal above \(F(\alpha)\), so \(F(\alpha)\) is achieved by N.

As an example, consider the following function: Let \(F(\alpha)\) be the least admissible ordinal above \(\alpha\). This function is obviously nondecreasing, and we will argue it's computable. Let \(\lambda'\) be the supremum of ordinals writable with \(\alpha\) as an oracle. From relativisation of results for \(\lambda\), it follows that \(\lambda'\) is accidentally writable with \(\alpha\) and is limit of admissibles. From that, there is an accidentally writable ordinal greater than \(F(\alpha)\). We can use universal machine U with oracle \(\alpha\) to seek for ordinals and then check if they are admissible greater than \(\alpha\). Checking admissibility is tricky, but we can just write \(L_\alpha\) (which is computable from \(\alpha\)) and see if it satisfies KP set theory axioms. If we find one, we seek for smaller ones greater than \(\alpha\). If there is none, we have just computed \(F(\alpha)\).

From this we see that achievable ordinals extend pretty far - since \(\lambda\) is achievable, \(\omega^1_{\lambda+1}\) is also achievable (from above theorem). We can easily extend this to least recursively inaccessible above \(\lambda\) and so on.

Theorem 12: \(\lambda^{0^\triangledown}\) is achievable.

We will simulate two machines: first one U eventually computes \(0^\triangledown\) like in proof of lemma 2. We also simulate machine from proof of theorem 2, which we denote M, but we allow it to use partial output of U as oracle. Again, if output of U changes, we restart M. Output of U at every stage before \(\lambda=\gamma\) will be computable, because there will be clockable ordinal larger than current stage which we can use to simulate U exactly up to that point. So before that stage the output of whole machine won't exceed \(\lambda\). At stage \(\lambda\), however, output of U will stabilize with \(0^\triangledown\) and M will work on full oracle. By argument from theorem 2 we will accidentally write \(\lambda^{0^\triangledown}>\lambda\) and no larger ordinal. Thus \(\lambda^{0^\triangledown}\) is achievable.

Theorem 13: Every \(0^\triangledown\)-writable ordinal is achievable.

Let U be as above. Note that at every stage below \(\lambda\) set of so far halted machines is computable (as clockables are unbounded in \(\lambda\)), and at stage \(\lambda=\gamma\) we already have full \(0^\triangledown\) written. Let machine M compute \(\alpha\geq\lambda\) from \(0^\triangledown\). We now allow M to use output of U so far. M restarts when output of U changes. Now, at every stage \(<\lambda\) so far output of U is computable, so M can't write an ordinal \(\geq\lambda\), and after stage \(\lambda\) M can work with full \(0^\triangledown\), so it computes \(\alpha\). So our composed machine computes only ordinals less that \(\lambda\) and \(\alpha\geq\lambda\), so it achieves \(\alpha\).

It follows that every ordinal not exceeding \(\lambda^{0^\triangledown}\) is achievable. Can we do better? Yes we can!

Theorem 14: Let \(\alpha\) be eventually writable ordinal. Every ordinal below \(\lambda^{0^{\triangledown^\alpha}}\) is achievable, where \(\triangledown^\alpha\) means transfinitely iterated lightface jump operator.

We proceed exactly as in theorem 13, but we use machine U which we prove to exist in lemma 5.

Theorem 15: Every eventually writable ordinal is achievable.

From lemma 6 we know that every ordinal \(\alpha<\zeta\) is below some \(\lambda^{0^{\triangledown^\beta}}\) for \(\beta<\zeta\), and every ordinal below \(\lambda^{0^{\triangledown^\beta}}\) is achievable, so \(\alpha\) is achievable.

Corollary 5: \(\zeta\) is the least unachievable ordinal. \(\zeta\leq\tau\leq\zeta+1\).

First part follows from theorems 6 and 15. Second claim uses theorem 7.

So now we have proved conjecture 1, because every sequence unbounded in \(\zeta\) consists of achievables. We have also learned everything we can about achievable ordinals, because they are exactly the eventually writable ordinals. Levels, however, are still quite a mystery. Question 1 still stands, and here is its extension:

Question 2: Is every level, other than \(\Sigma\), eventually writable? Is there an ITTM which accidentally writes some ordinals above \(\zeta\), but not all of them?

Update

Theorem 16: Suppose M is an ITTM and ordinals accidentally written by M are upper bounded by an accidentally writable ordinal. Then they are upper bounded by an eventually writable ordinal.

Run a universal machine U. Whenever it produces an accidentally writable ordinal \(\alpha\), write it to the output, pause simulation of U and start running M from the empty tape. If we see that M accidentally writes an ordinal greater than \(\alpha\), stop simulating it and continue simulating U. By assumption, at one point U will write ordinal \(\beta\) greater than anything that M writes, which means that when we start simulating M, the computation will just keep going forever, and output with stabilize with \(\alpha\) on the output, making it eventually writable.

Corollary 6: Let \(\alpha<\Sigma\) be a level. Then \(\alpha<\zeta\). Hence \(\tau=\zeta\).

Let M be a machine with level \(\alpha\). Then \(\alpha\) is an accidentally writtable upper bound on ordinals accidentally writable by M, so by theorem 16, there is an upper bound which is less than \(\zeta\). But clearly \(\alpha\) is the least upper bound, making \(\alpha<\zeta\). In particular, \(\zeta\) is not a level, and by theorem 15, every smaller ordinal is a level, so by definition, \(\tau=\zeta\).

Last sentence of above proof shows that answer to question 1 is affirmative, and theorem 16 shows that so is the answer to the first part of question 2. The second part is true for a different reason: we can modify a universal machine to only write successor ordinals, and this machine will write, for example, \(\zeta+1\), but not \(\zeta+\omega\).

Corollary 7: If an ITTM accidentally writes ordinals unbounded in \(\zeta\), then it accidentally writes ordinals unbounded in \(\Sigma\). Same if an ITTM accidentally writes an ordinal which isn't eventually writable.

This is simply the contrapositive of theorem 16,

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.