Logical Approaches to Computational Barriers

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 |