Difference between revisions of "Infinite time Turing machines"
Line 3: | Line 3: | ||
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. | 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. | + | 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 <cite>HamkinsLewis2000:InfiniteTimeTM, Hamkins2002:Turing, Hamkins2004:SupertaskComputation</cite> |
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. | 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. | ||
Line 11: | Line 11: | ||
* $\Sigma=$ the supremum of the accidentally writable ordinals | * $\Sigma=$ the supremum of the accidentally writable ordinals | ||
− | Hamkins and Lewis showed that $\lambda\lt\zeta\lt\Sigma$, and while $\lambda$ and $\zeta$ are [[admissible]] ordinals and [[admissible#Computably inaccessible ordinal | computably inaccessible]], $\Sigma$ is not admissible. | + | Hamkins and Lewis <cite>HamkinsLewis2000:InfiniteTimeTM</cite> showed that $\lambda\lt\zeta\lt\Sigma$, and while $\lambda$ and $\zeta$ are [[admissible]] ordinals and [[admissible#Computably inaccessible ordinal | computably inaccessible]], $\Sigma$ is not admissible. |
− | Welch 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. | + | Welch <cite>Welch2000:LengthsOfITTM, Welch2000:Eventually</cite> 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. |
+ | |||
+ | |||
+ | {{References}} |
Revision as of 07:23, 5 January 2012
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 [1, 2, 3]
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 [1] showed that $\lambda\lt\zeta\lt\Sigma$, and while $\lambda$ and $\zeta$ are admissible ordinals and computably inaccessible, $\Sigma$ is not admissible.
Welch [4, 5] 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.
References
- Hamkins, Joel David and Lewis, Andy. Infinite time Turing machines. J Symbolic Logic 65(2):567--604, 2000. www arχiv DOI MR bibtex
- Hamkins, Joel David. Infinite time Turing machines. Minds and Machines 12(4):521--539, 2002. (special issue devoted to hypercomputation) www arχiv bibtex
- Hamkins, Joel David. Supertask computation. Classical and new paradigms of computation and their complexity hierarchies23:141--158, Dordrecht, 2004. (Papers of the conference ``Foundations of the Formal Sciences III'' held in Vienna, September 21-24, 2001) www arχiv DOI MR bibtex
- Welch, Philip. The Lengths of Infinite Time Turing Machine Computations. Bulletin of the London Mathematical Society 32(2):129--136, 2000. bibtex