Series: Penn State Logic Seminar Date: Tuesday, February 6, 2001 Time: 2:30 - 3:20 PM Place: 316 Willard Building Speaker: Joel Hamkins, CUNY, Mathematics Title: Infinite Time Turing Machines Abstract: In these days of super-fast computers whose speed seems to be increasing without bound, we are perhaps pushed to wonder: what could we compute with an INFINITELY fast computer? By proposing a natural model for supertasks---computations with infinitely many steps---I will provide in this talk a theoretical foundation on which to answer this question. The model is simple: I simply extend the Turing machine concept into transfinite ordinal time. The resulting machines can perform infinitely many steps of computation, and go on to more computation after that. But mechanically they work just like Turing machines. In particular, they have the usual Turing machine hardware; there is still the same smooth infinite paper tape and the same mechanical head moving back and forth according to a finite algorithm, with finitely many states. What is new is the definition of the behavior of the machine at limit ordinal times. The resulting computability theory leads to a notion of computation on the reals, concepts of decidability and semi-decidability for sets of reals as well as individual reals, two kinds of jump-operator, and a notion of relative computability using oracles which gives a rich degree structure on both the collection of reals and the collection of sets of reals. Many interesting open questions remain.
Mathematical Logic at Penn State
Department of Mathematics