pith. sign in

arxiv: math/9907044 · v1 · submitted 1999-07-07 · 🧮 math.LO

Infinite time Turing machines with only one tape

classification 🧮 math.LO
keywords computablefunctionsinfinitetimeclassclockablemachineone-tape
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.