Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Space Complexity in Ordinal Turing Machines

Speaker: Joost Winter
Slot: Array, 12:00-12:20, col. 2


We introduce time and space complexity classes of the P and PSPACE families for
ordinal Turing Machines by Peter Koepke. We establish a number of connections
between these classes internally, and between these classes and the earlier
defined time-complexity classes for infinite time Turing machines as defined by
Joel Hamkins and Andy Lewis. Furthermore, we give a partial negative answer to
the question whether these space complexity classes can somehow be related to
the ITTM degrees defined by Hamkins/Lewis.

websites: Arnold Beckmann 2008-05-19