BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Merlin Carl (Europa-Universität Flensburg)
DTSTART:20210406T080000Z
DTEND:20210406T093000Z
DTSTAMP:20260423T004910Z
UID:CTA/54
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CTA/54/">Com
 plexity and Decision Times for ITTMs - The Story of the Bold Conjecture</a
 >\nby Merlin Carl (Europa-Universität Flensburg) as part of Computability
  theory and applications\n\n\nAbstract\nInfinite Time Turing Machines (ITT
 Ms)\, defined in the classical paper by Hamkins and Lewis\, allow Turing m
 achines to run for transfinite ordinal time. One can then generalize notio
 ns of time (Schindler) and space (Löwe) complexity to this setting. Löwe
 's "bold conjecture" was whether the two notions are non-trivially connect
 ed\, i.e.\, whether low space complexity implies low time complexity. In o
 ur talk\, we will show that this conjecture fails. Showing this will\, how
 ever\, leads naturally to a systematics study of decision and semi-decisio
 n times on ITTMs\, which was done in joint work with Philipp Schlicht and 
 Philip Welch and led to connections with descriptive set theory and genera
 lizations to the theory of ranks.\n\nJoint work with Philipp Schlicht and 
 Philip Welch.\n
LOCATION:https://researchseminars.org/talk/CTA/54/
END:VEVENT
END:VCALENDAR