Post's problem for supertasks has both positive and negative solutions
classification
🧮 math.LO
keywords
theredegreesjumpsupertaskcontextinfinitenegativepositive
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.