Infinite Time Turing Machines
Hamkins, Joel David ; Lewis, Andy
J. Symbolic Logic, Tome 65 (2000) no. 1, p. 567-604 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.
Publié le : 2000-06-14
Classification:  
@article{1183746064,
     author = {Hamkins, Joel David and Lewis, Andy},
     title = {Infinite Time Turing Machines},
     journal = {J. Symbolic Logic},
     volume = {65},
     number = {1},
     year = {2000},
     pages = { 567-604},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746064}
}

Hamkins, Joel David; Lewis, Andy. Infinite Time Turing Machines. J. Symbolic Logic, Tome 65 (2000) no. 1, pp.  567-604. http://gdmltest.u-ga.fr/item/1183746064/