The ordinals of infinite time Turing machines

The theory of infinite time Turing machines extends the operation of ordinary Turing machines into transfinite ordinal time. At successor stages of computations, the machines compute as expected, according to the rigid instructions of their finite programs, writing on the tape, moving the head to the left or right and changing to a new state. At limit stages, the information the computation was producing is preserved in a sense: each cell of the tape assumes the limsup of its values going into that limit; the head is reset to the left-most cell and the state is placed in the limit state, a distinguished state like the start state and the halt state.

A real is writable by such machines if there is a program which on trivial input can write that real on the output tape and then halt. A real is eventually writable if there is a program that on trivial input can write the real on the output tape in such a way that from some point on, the output tape exhibits that real as its final stabilized value, even if the machine does not halt. A real is accidently writable if it appears on one of the tapes during the course of a computation of a program on trivial input. See (Hamkins & Lewis, 2000; Hamkins, 2002; Hamkins, 2004)

Similarly, an ordinal is writable or eventually writable or accidentally writable if it is the order type of a relation coded by such a kind of real.

• $\lambda=$ the supremum of the writable ordinals
• $\zeta=$ the supremum of the eventually writable ordinals
• $\Sigma=$ the supremum of the accidentally writable ordinals

Hamkins and Lewis (Hamkins & Lewis, 2000) showed that $\lambda\lt\zeta\lt\Sigma$, and while $\lambda$ and $\zeta$ are admissible ordinals and computably inaccessible, $\Sigma$ is not admissible.

Welch (Welch, 2000) proved the $\lambda-\zeta-\Sigma$ theorem, asserting that $L_\lambda\prec_{\Sigma_1}L_\zeta\prec_{\Sigma_2}L_\Sigma$, and furthermore $\lambda$ is the least ordinal such that $L_\lambda$ has a $\Sigma_1$-elementary end-extension, and $\zeta$ is least such that $L_\zeta$ has a $\Sigma_2$-elementary end-extension.

References

1. Hamkins, J. D., & Lewis, A. (2000). Infinite time Turing machines. J. Symbolic Logic, 65(2), 567–604. https://doi.org/10.2307/2586556
2. Hamkins, J. D. (2002). Infinite time Turing machines. Minds and Machines, 12(4), 521–539. http://boolesrings.org/hamkins/turing-mm/
3. Hamkins, J. D. (2004). Supertask computation. Classical and New Paradigms of Computation and Their Complexity Hierarchies, 23, 141–158. https://doi.org/10.1007/978-1-4020-2776-5_8
4. Welch, P. (2000). The Lengths of Infinite Time Turing Machine Computations. Bulletin of the London Mathematical Society, 32(2), 129–136.

Main library