1998/08/31 by Joel David Hamkins, Andrew Lewis, Hamkins, Joel David +2
Computer Science · Mathematics · #03D30 #03D60 #Benford’s Law and Fraud Detection #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D30 #msc:03D60
paper · pdf · doi:10.48550/arxiv.math/9808128
20 pages, submitted to the Archive for Mathematical Logic. See the author's home pages at http://www.library.csi.cuny.edu/users/hamkins and http://saturn.vcu.edu/~amlewis
arxiv created 1998/08/31 · openalex publication_date 1998/08/31 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 0jump, has in a sense both positive and negative solutions. Namely, in the context of the reals there are no degrees between 0 and 0jump, 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.