Set Theory and Topology seminar (BGU)

Time: Tuesday, March 10, 12:15-13:40.

Place: Seminar room -101, Math building 58.

Speaker: Philipp Schlicht (Bonn).

Title: Infinite time machines.

Abstract: In recent years, various types of infinite time Turing machines and automata were studied by Hamkins, Welch, Koepke and others. The programs are identical to those of finite time machines, but the time and the tape are ordinal numbers, for instance a machine may continue after infinitely many steps and halt at some infinite stage. Some motivations to study these machines include the possibility to refine results in descriptive set theory and higher computability theory, and to prove analogues to classical results for Turing machines. In recent work with Merlin Carl, we found connections between infinite time machines, algorithmic randomness, and inner model theory. I will begin with an introduction to infinite time machines. I will then discuss more recent results, for instance analogues to the following classical theorem of Sacks: if an infinite sequence with values 0 and 1 is computable relative to every oracle in a set of sequences with positive Lebesgue measure, then it is already computable.