Infinite time Turing machines with only one tape (Q2720332)

In this paper the authors compare the computational powers of one-tape and multi-tape infinite time Turing machines. The infinite time Turing machines of three tapes (input/scratch/output) were introduced by the first author and \textit{A. Lewis} [``Infinite time Turing machines'', J. Symb. Log. 65, 567-604 (2000; Zbl 0963.03064)]. An infinite time Turing machine is an ordinary Turing machine equipped with a new ``limit'' state. The authors point out that the machines with only one tape are in many respects as powerful as their multi-tape cousins. By simulating three-tape machines using one-tape machines, they show that the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions \(f: R\to N\), the same class of computable functions. They also show that every ordinal that 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. Nevertheless, the one-tape machines are not fully as powerful as multi-tape machines. An example of a computable function \(f: R\to R\) which is not one-tape computable is presented. Yet the authors show that the closure under composition of the class of one-tape computable functions yields the full class of all infinite time computable functions.