Infinite time Turing machine: Difference between revisions
Jump to navigation
Jump to search
Content added Content deleted
(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 |
||
Line 12: | Line 12: | ||
* \(\Sigma\) is the least ordinal so that \(\zeta\) is \(\Sigma\)-\(\Sigma_2\)-stable. |
* \(\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}\). |
<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> |