Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Space Complexity in Ordinal Turing Machines

Edit abstract data

Speaker: Joost Winter
Slot: Tue, 12:00-12:20, Amphitheater B (col. 2)

Abstract

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 Valid HTML 4.01! Valid CSS!