Infinite time Turing machine
The infinite time Turing machines are a powerful method of computation introduced by Joel David Hamkins and Andy Lewis.[1] They augment the normal notion of a Turing machine (first introduced by Alan Turing in his seminal paper[2]), to a hypothetical machine model which can run for infinitely many steps. It separates the tape into three separate tapes - the input, scratch and output tapes. It's possible to define an analogue of the busy beaver function for ITTMs, denoted \(\Sigma_\infty\), which grows significantly faster than the ordinary busy beaver function, even with an oracle, as well as a halting problem for ITTMs, which has higher Turing degree than \(0^{(\alpha)}\) for all \(\alpha < \gamma\), where \(\gamma\) is the second of the following large ITTM-related ordinals:
- \(\lambda\) is the supremum of all ordinals which are the output of an ITTM with empty input.
- \(\gamma\) is the supremum of all halting times of an ITTM with empty input.
- \(\zeta\) is the supremum of all ordinals which are the eventual output of an ITTM with empty input.
- \(\Sigma\) is the supremum of all ordinals which are the accidental output of an ITTM with empty input.
The ITTM theorem says that \(\lambda = \gamma\), and that:
- \(\lambda\) is \(\zeta\)-stable (i.e. \(\zeta\)-\(\Sigma_1\)-stable).
- \(\zeta\) is the least ordinal which is \(\rho\)-\(\Sigma_2\)-stable for some \(\rho > \zeta\).
- \(\Sigma\) is the least ordinal so that \(\zeta\) is \(\Sigma\)-\(\Sigma_2\)-stable.
This further shows the computational potency of ITTMs, since the limit of the order-types of well-orders they can compute is much greater than that of normal TMs, i.e. \(\omega_1^{\mathrm{CK}\).