Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.

View the Project on GitHub neugierde/cantors-attic

**Quick navigation**

The upper attic

The middle attic

The lower attic

The parlour

The playroom

The library

The cellar

**Sources**

Cantor's Attic (original site)

Joel David Hamkins blog post about the Attic

Latest working snapshot at the wayback machine

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.

- Hamkins, J. D., & Lewis, A. (2000). Infinite time Turing machines.
*J. Symbolic Logic*,*65*(2), 567–604. https://doi.org/10.2307/2586556 - Hamkins, J. D. (2002). Infinite time Turing machines.
*Minds and Machines*,*12*(4), 521–539. http://boolesrings.org/hamkins/turing-mm/ - 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 - Welch, P. (2000). The Lengths of Infinite Time Turing Machine Computations.
*Bulletin of the London Mathematical Society*,*32*(2), 129–136.