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.