Hauptseminar Mathematische Logik und Theoretische Informatik

Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in SR 1 des Gebäudes INF 205.
(The talks are usually on Tuesday at 4 p.m. in SR 1 of building INF 205.)


 

Vorträge im
SoSe 2018

24. April 2018
Nan Fang, Universität Heidelberg
When the saving strategy works


12. Mai 2018
Thibaud Schmidt, Universität Heidelberg
Basic Fuzzy Logic


26. Juni 2018
Nan Fang, Universität Heidelberg
Monotonous betting strategies in warped casinos


15. August 2018
Leyla Kibar, Universität Heidelberg
0-1 Gesetz der Logik - Eine Einführung und Zusammenfassung wichtiger Ergebnisse in Logiken erster und zweiter Stufe


15. August 2018
Akin Ünal, Universität Heidelberg
Das Entscheiden von Paritätsspielen in Quasi-Polynomieller Zeit


16. August 2018
Valentino Delle Rose, University of Rome, La Sapienza
Left-c.e. reals and Martin-Löf randomness


20. September 2018
Rebecca Schönberger, Universität Heidelberg
Die Prioritätsmethode zur Konstruktion rekursiv aufzählbarer Mengen


 



15. August

0-1 Gesetz der Logik - Eine Einführung und Zusammenfassung wichtiger Ergebnisse in Logiken erster und zweiter Stufe

 
Diese Arbeit ist einerseits eine Einführung in das Feld der 0-1 Gesetze, andererseits eine Zusammenstellung zentraler und wichtiger Ergebnisse in Teilen der Logiken erster sowie zweiter Stufe. Grundlage des 0-1 Gesetzes ist die Überlegung einem Satz \(\varphi\) einer relationalen Sprache eine Wahrscheinlichkeit \(\mu_n(\varphi)\) zuzuordnen. Diese ist in vorliegender Arbeit als Gleichverteilung auf allen Strukturen mit Trägern der Kardinalität \(n\) definiert und beschreibt den Anteil der Strukturen, bezüglich derer \(\varphi\) wahr ist. Die asymptotische Wahrscheinlichkeit, dass ein entsprechender Satz in einer beliebigen endlichen Struktur gilt, wird mit \(\mu(\varphi):=\lim_{n\to\infty}\mu_{n}(\varphi)\) beschrieben, falls der Limes existiert. Einer Logik kommt genau dann die Eigenschaft zu das 0-1 Gesetz zu erfüllen, wenn jeder in ihr ausdrückbarer Satz entweder asymptotische Wahrscheinlichkeit 0 oder 1 besitzt, das heißt, wenn \(\mu(\varphi)\in\{0,1\})\). Fagin (1976) und undabhängig davon Glebskii, Kogan, Liogonskii und Talanov (1969) waren die Ersten, die solch ein Gesetz formulierten und für die Prädikatenlogik erster Stufe (\(FO\)) bewiesen. Es wird in dieser Arbeit gezeigt, dass besagtes Gesetz für die Logiken \(FO\), \(L^{\omega}_{\infty\omega}\), die einstellige \(MSO\), \(\Sigma^1_1\)(Ackermann) und \(\Sigma^1_1\)(Bernays-Schönfinkel) gelten. Negative Ergebniss werden für \(L_{\infty\omega}\), \(MSO\) und \(\Sigma^1_1\)(Gödel ohne Gleichheit) erreicht.


16. August

Left-c.e. reals and Martin-Löf randomness

 
The aim of the thesis is to discuss in detail the most classical notion of algorithmic randomness, namely Martin-Löf randomness, focusing in particular on the role played by left-c.e. reals within the concerning theory, which turns out to be similar in spirit to the one played by c.e. sets in classical computability.
For this purpose, we highlight the charcterization of the left-c.e. reals as the halting probabilities of the prefix-free machines. Then, a strong hint of the deep connection between left-c.e. reals and Martin-Löf randomness comes directl by the definition of the latter via the prefix-free Kolmogorov complexity. Indeed, this definition implies the choice of a preifx-free universal machine, whose halting probability \(\Omega\) is a Martin-Löf random left-c.e. real. Furthermore, \(\Omega\) turns out to be Solovay complete.
The most intersting result we present, which clarifies the similarities mentioned above, is a characterization of Martin-Löf random left-c.e. reals: they are precisely the halting probabilities of universal prefix-free machines, and also precisely the Solovay complete reals. By stressing the parallel of the latter result with Myhill's Theorem, we can look at Martin-Löf random left-c.e. reals as analogous, with algorithmic randomness, to (the different versions of) the halting problem.