Abstract

The infinite time Turing machine analogue of Post's problem, the question whether there are semi-decidable supertask degrees between 0 and the supertask jump 0∇, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between 0 and 0∇, 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