Infinite Time Turing Machines

Details Infinite Time Turing Machines Infinite Time Turing Machines

1998-08-21

arxiv.org/abs/math/9808093v1

Mathematics

Logic

57 pages, 4 figures, to appear in the Journal of Symbolic Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Infinite Time Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infinite Time Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite Time Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21403