Hauptseminar Mathematische Logik und Theoretische Informatik

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


 

Vorträge

23. April 2013

Gerrit Schumacher, Universität Heidelberg
Aufzählungsreduzierbarkeit und die Aufzählungsgrade

7. Mai 2013

Ivan Titov, Universität Heidelberg
Vollständigkeitsbegriffe für die Exponentialzeitklassen

21. Mai 2013

Martin Monath, Universität Heidelberg
Die Nichtdichtheit der rekursiv aufzählbaren ibT-Grade

11. Juni 2013

Nadine Losert, Universität Heidelberg
Die linear beschränkten Turinggrade

18. Juni 2013

Rupert Hölzl, Universität der Bundeswehr München
Absolutely undecidable sets

25. Juni 2013

Jan Geiger, Universität Heidelberg
Introreduzierbarkeit und Introimmunität

9. Juli 2013

Klaus Ambos-Spies, Universität Heidelberg
Uniform rekursiv beschränkte Turingreduzierbarkeiten

16. Juli 2013

Jana Mille, Universität Heidelberg
Effektive Quantorenelimination

 



23. April

Aufzählungsreduzierbarkeit und die Aufzählungsgrade

 
Dieser Vortrag befasst sich mit einer Reduzierbarkeit, die den Begriff der Aufzählbarkeit von Mengen relativiert. Man könnte sagen, dies ist eine Verallgemeinerung der Turingreduzierbarkeit, die ja den Begriff der Berechenbarkeit relativiert. Weiterhin gibt es einen engen Bezug zu der Relation "rekursiv aufzählbar in" und zu einer weiteren Reduzierbarkeit, der "nichtdeterministischen Turingreduzierbarkeit". Aufgrund der Reflexivität und Transitivität der Aufzählungsreduzierbarkeit kann man eine Gradstruktur und auch einen Jump-Operator, ähnlich dem Turingjump, definieren. Diese Struktur weist auch einige Ähnlichkeiten zu den Turinggraden auf. Es wird sich herausstellen, das es sogar eine Unterstruktur der Aufzählungsgrade gibt, die isomorph zur Struktur der Turinggrade ist.

21. Mai

Die Nichtdichtheit der rekursiv aufzählbaren ibT-Grade

 
Im kommenden Vortrag stelle ich einen Teil meiner Diplomarbeit vor, genauer werde ich ein Ergebnis von George Barmpalias und Andrew E.M. Lewis präsentieren. Sie haben 2005 gezeigt, dass die partielle Ordnung der rekursiv aufzählbaren ibT-Grade nicht dicht ist. Ziel ist es, an diesem Beispiel aufzuzeigen, wie man mit Hilfe von Baumkonstruktionen, einer Art Infinite-Injury-Konstruktion, an solche Problemstellungen herangehen kann.

11. Juni

Die linear beschränkten Turinggrade

 
Ich werde meine Zulassungsarbeit über die linear beschränkten aufzählbaren Turing-Grade vorstellen. Ich werde die Eigenschaften der partiellen Ordnung auf diesen Graden aufzeigen und dabei genauer auf den Beweis der Distributivität eingehen. Außerdem werde ich verschiedene Transfertechniken präsentieren, mit Hilfe derer sich Ergebnisse über andere Turing-Reduzierbarkeiten auf die linear beschränkte Turing-Reduzierbarkeit übertragen lassen.

18. Juni

Absolutely undecidable sets

 
An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. Downey, Jockusch and Schupp asked whether, unlike the case for bi-immunity, there is an absolutely undecidable set in every non-zero Turing degree. We provide a positive answer to this question by applying techniques from coding theory. We show how to use Walsh-Hadamard codes to build a truth-table functional which maps any real A to a real B such that given B on a set of positive upper density, one can recover A. This implies that if A is non-computable, then B is absolutely undecidable.(Joint work with Laurent Bienvenu and Adam Day.)

25. Juni

Introreduzierbarkeit und Introimmunität

 
Für eine gegebene Reduzierbarkeit nennt man eine unendliche Menge introreduzierbar, wenn die Menge auf jede ihrer unendlichen Teilmengen reduziert werden kann, und introimmun, wenn die Menge auf keine ihrer unendlichen Teilmengen reduziert werden kann. Diskutiert wird die Frage, ob es für die typischen Reduzierbarkeiten in der Berechenbarkeitstheorie nichtrekursive introreduzierbare beziehungsweise introimmune Mengen gibt.

9. Juli

Uniform rekursiv beschränkte Turingreduzierbarkeiten

 
Jede uniform rekursive Klasse F 1-stelliger Funktionen definiert eine uniform rekursiv beschränkte Turingreduzierbarkeit (kurz: ubT-Reduzierbarkeit), wobei eine Menge A auf eine Menge B F-T-reduzierbar ist, falls es eine Turingreduktion von A auf B gibt, deren Usefunktion durch eine Funktion aus der betrachteten Funktionenklasse beschränkt ist. In unserem Vortrag diskutieren wir einige allgemeinen Aspekte der ubT-Reduzierbarkeiten und deren rekursiv aufzählbaren (r.a.) Grade. Insbesondere charakterisieren wir die Stärke der ubT-Reduzierbarkeiten durch das Wachstumsverhalten der Funktionen in den induzierenden Klassen und geben eine entsprechende Charakterisierung der zulässigen ubT-Reduzierbarkeiten, d.h. der Reduzierbarkeiten die reflexiv und transitiv sind und daher eine partielle Ordnung auf den r.a. Mengen definieren. Schliesslich charakterisieren wir die zulässigen ubT-Reduzierbarkeiten, für die die partielle Ordnung der r.a. Grade ein größtes Element besitzt (d.h. für die es vollständige Mengen gibt) bzw. für die die partielle Ordnung der r.a. Grade ein oberer Halbverband ist. Dabei zeigt sich, dass für jede zulässige ubT-Reduzierbarkeit, für die die r.a. Grade einen oberen Halbverband bilden, dieser auch ein größtes Element besitzt, wogegen die Umkehrung i.A. nicht gilt.

16. Juli

Effektive Quantorenelimination

 
Eine formale Sprache lässt Quantorenelimination zu, wenn jede über dem entsprechenden Alphabet formulierte Aussage zu einer äquivalenten, quantorenfreien Aussage umgeformt werden kann. Diese Eigenschaft nennen wir zusätzlich effektiv, wenn es einen deterministischen Algorithmus für die Überführung gibt. In meinem Vortrag, der im Rahmen eines Bachelor-Seminars abgehalten wird, werde ich auf die Beziehungen zwischen (effektiver) Quantorenelimination innerhalb und Entscheidbarkeit von Theorien über formalen Sprachen eingehen. Dabei werde ich insbesondere Sprachen mit mindestens einer Konstanten, einer Relation und einer Funktion, sowie das Beispiel der Z-Strukturen, näher behandeln.