Infinite time Turing machines with only one tape

Details Infinite time Turing machines with only one tape Infinite time Turing machines with only one tape

1999-07-07

arxiv.org/abs/math/9907044v1

Mathematics

Logic

21 pages, 4 figures

Scientific paper

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions f:R-->N, the same class of computable functions. Nevertheless, there are infinite time computable functions f:R-->R that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal which is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.

Affiliated with

Also associated with

No associations

Rating

Infinite time Turing machines with only one tape 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 with only one tape, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite time Turing machines with only one tape will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-357801