Infinite time Turing machine: Difference between revisions
no edit summary
(Created page with "The infinite time Turing machines are a powerful method of computation introduced by Joel David Hamkins and Andy Lewis.<ref>Infinite Time Turing Machines, Joel David Hamkins and Andy Lewis, 1998</ref> They augment the normal notion of a Turing machine (first introduced by Alan Turing in his seminal paper<ref>Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''.</ref>), to a hypot...") |
No edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 5:
* \(\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.<ref>J. D. Hamkins, A. Lewis, "[https://arxiv.org/abs/math/9808093 Infinite Time Turing Machines]", arXiv 9808093 (2008). Accessed 1 September 2023.</ref><sup>theorem 2.2</sup>
The ITTM theorem says that \(\lambda = \gamma\), and that:
Line 12 ⟶ 14:
* \(\Sigma\) is the least ordinal so that \(\zeta\) is \(\Sigma\)-\(\Sigma_2\)-stable.
<nowiki>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}}\).</nowiki>
Infinite time Turing machines can themselves be generalized further to \(\Sigma_n\)-machines, with \(\Sigma_2\)-machines being the same as the original.<ref>Friedman, Sy-David & Welch, P. D. (2011). Hypermachines. Journal of Symbolic Logic</ref>
| |||