[bibtex key=HamkinsWelch2003:PfneqNPf]
Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines
[bibtex key=HamkinsWelch2003:PfneqNPf]
Abstract. We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines
[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
[bibtex key=Hamkins2002:Turing]
This is a survey of the theory of infinite time Turing machines.
Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.
[bibtex key=HamkinsSeabold2001:OneTape]
Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions
[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