|
Julia Osthues

Dr. Philipp Schlicht (Universität Bonn): Vortrag: Infinite time machines

Wednesday, 18.03.2015 11:00 im Raum Hörsaal M6

Mathematik und Informatik

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, 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.



Angelegt am Friday, 06.03.2015 12:47 von Julia Osthues
Geändert am Friday, 06.03.2015 12:47 von Julia Osthues
[Edit | Vorlage]

Sonstige Vorträge