Post's problem for supertasks has both positive and negative solutions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Recently we have introduced a new model of infinite computation by extending the operation of ordinary Turing machines into transfinite ordinal time. In this paper we will show that the infinite time Turing machine analogue of Post's problem, the question whether there are supertask degrees between 0 and the supertask jump 0^jump, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between 0 and 0^jump, but in the context of SETS of reals, there are; indeed, there are incomparable semi-decidable supertask degrees. Both arguments employ a kind of transfinite-injury construction which generalizes canonically to oracles.
20 pages, submitted to the Archive for Mathematical Logic. See the author's home pages at http://www.library.csi.cuny.edu/users/hamkins and http://saturn.vcu.edu/~amlewis

Keywords

Logic, 03D30; 03D60

Citation

URI

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

Consulte el texto completo en el siguiente enlace:

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

Collections

arXiv