Infinite time Turing machines with only one tape

Simple item page
dc.creatorHamkins, Joel David
dc.creatorSeabold, Daniel Evan
dc.date1999-07-07
dc.date.accessioned2026-07-07T05:29:49Z
dc.date.available2026-07-07T05:29:49Z
dc.descriptionInfinite 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.
dc.description21 pages, 4 figures
dc.identifierhttps://arxiv.org/abs/math/9907044
dc.identifierhttp://arxiv.org/abs/math/9907044
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/78787
dc.subjectLogic
dc.subject03D10; 03D60
dc.titleInfinite time Turing machines with only one tape
dc.typetext

Files

Collections

arXiv