pith. sign in

arxiv: math/9808128 · v1 · submitted 1998-08-31 · 🧮 math.LO

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

classification 🧮 math.LO
keywords theredegreesjumpsupertaskcontextinfinitenegativepositive
0
0 comments X
read the original abstract

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.

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.