Space and time complexity for Infinite Time Turing Machines
Logic and Set Theory Seminar
6th December 2023, 3:30 pm – 4:30 pm
, Zoom https://bristol-ac-uk.zoom.us/j/97141948018
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.