Infinite Time Turing Machines

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual 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 reals and sets of reals and a rich degree structure, stratified by two natural jump operators.
57 pages, 4 figures, to appear in the Journal of Symbolic Logic

Keywords

Logic, 03D30; 03D60

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/77307

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/9808093
 http://arxiv.org/abs/math/9808093

Collections

arXiv