Infinite time Turing machine

The infinite time Turing machines are a powerful method of computation introduced by Joel David Hamkins and Andy Lewis. They augment the normal notion of a Turing machine (first introduced by Alan Turing in his seminal paper), 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.

ITTMs are quote potent computational models, as they are able to decide whether a given relation on \(\mathbb N\) is a well-order or not.^{theorem 2.2}

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}}\).

Infinite time Turing machines can themselves be generalized further to \(\Sigma_n\)-machines, with \(\Sigma_2\)-machines being the same as the original.