[bibtex key=HamkinsMiller2009:PostsProblemForORMsExplicitApproach]
We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.
[bibtex key=HamkinsMiller2007:PostsProblemForORMs]
We study Post’s Problem for ordinal register machines, showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors earlier results for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.
[bibtex key=HamkinsLewis2002:PostProblem]
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^\triangledown$, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between $0$ and $0^\triangledown$, 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.