Merlin Carl

Space and time complexity for Infinite Time Turing Machines

Infinite Time Turing Machines (ITTMs), defined in the classical paper by Hamkins and Lewis, allow Turing machines to run for transfinite ordinal time. One can then generalize notions of time (Schindler) and space (Löwe) complexity to this setting. Löwe's "bold conjecture" was whether the two notions are non-trivially connected, i.e., whether low space complexity implies low time complexity. In our talk, we will show that this conjecture fails. Showing this will, however, leads naturally to a systematic study of decision and semi-decision times on ITTMs, which was done in joint work with Philipp Schlicht and Philip Welch and led to connections with descriptive set theory and generalizations to the theory of ranks.