Tag Archives: Andrew Lewis

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

Posted on by
Reply

[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▽, 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.

Infinite time Turing machines

Posted on by
1

[bibtex key=HamkinsLewis2000:InfiniteTimeTM]

This is the seminal paper introducing infinite time Turing machines.

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual reals. Every Π11 set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the Δ21 sets. Our oracle concept leads to a notion of relative computability for reals and sets of reals and a rich degree structure, stratified by two natural jump operators.