Infinite time Turing machines with only one tape

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
21 pages, 4 figures

Keywords

Logic, 03D10; 03D60

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/78787

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/9907044
 http://arxiv.org/abs/math/9907044

Collections

arXiv