The Journal of Symbolic Logic

Research Article

Infinite time Turing machines

Joel David Hamkinsa1 and Andy Lewisa2

a1 Department of Mathematics, City University of New York, College of Staten Island, Staten Island, NY 10314., USA, E-mail: hamkins@postbox.csi.cuny.edu

a2 Department of Mathematics, Virginia Commonwealth University, Box #842014, Richmond, VA. 23284-2019, E-mail: amlewis@saturn.vcu.edu

Abstract

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. Every set. for example, is decidable by such machines, and the semi-decidable sets form a portion of the sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

(Received June 18 1997)

(Revised March 09 1998)