Complexity and Decision Times for ITTMs - The Story of the Bold Conjecture

Abstract: 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 systematics 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.

Joint work with Philipp Schlicht and Philip Welch.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.