Oberseminar

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


Oberseminar Mathematische Logik und Theoretische Informatik 

 

 

Vorträge

23. Oktober 2012

Wolfgang Merkle, Universität Heidelberg 

Ein vollständiger Grad für die rekursiv aufzählbaren K-Grade

 

13. November 2012

Martin Ziegler, TU Darmstadt 

Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability

 

20. November 2012

Thorsten Kräling, Universität Heidelberg

Classification Problems in the Time Hierarchy

 

11. Dezember 2012

Franziska Freyer, Universität Heidelberg

Das Post'sche Problem (Teil I)

 

15. Januar 2013

Franziska Freyer, Universität Heidelberg

Das Post'sche Problem (Teil II)

 

22. Januar 2013

Wolfgang Merkle, Universität Heidelberg

Information und Größe

 

29. Januar 2013

Philipp Geiger, Universität Heidelberg

Eine Erweiterung von Gödels Unvollständigkeitsthese

 

5. Februar 2013

Klaus Ambos-Spies, Universität Heidelberg

Maximal Pairs and Array Noncomputability

 

 

 

23. Oktober

 

 

 

 

 

 

 

 

 

 

 

 

       

Ein vollständiger Grad für die rekursiv aufzählbaren K-Grade

 
In der algorithmischen Zufälligkeit werden verschiedene Zufälligkeitsbegriffe für unendliche Binärfolgen, kurz Folgen, betrachtet. Viele dieser Begriffe können durch die Kolmogorov-Komplexität der Anfangsstücke der betrachteten Folge beschrieben werden. Es liegt dann nahe, Folgen hinsichtlich der Komplexität ihrer Anfangsstücke zu vergleichen und entsprechende Reduzierbarkeiten zu definieren. Beispielsweise heißt eine Folge K-reduzierbar auf eine andere Folge, falls bis auf eine additive Konstante für alle Längen das Anfangsstück der gegebenen Länge der ersten Folge höchstens so große Kolmogorov-Komplexität hat wie das Anfangsstück derselben Länge der zweiten Folge.   
 
Der Vortrag stellt zunächst die K-Reduzierbarkeit vor und eine Reihe von damit verwandten Relationen, etwa die Solovay- und die identitätsbeschränkte Turing-Reduzierbarkeit, sowie die Reduzierbarkeit vom effektiven Lipschitz-Typ. Es werden dann bekannte Zusammenhänge zwischen diesen und weiteren Reduzierbarkeiten behandelt und das neuere Ergebnis von Barmpalias et al., dass die rekursiv aufzählbaren K-Grade ein größtes Element besitzen.
 
 
20. November 
 

A classification problem is a tuple (X_0, ..., X_m) of disjoint sets of nonnegative integers. Given some input z which is in the union of these sets, we want to compute the unique k such that z is in X_k. If, for all such inputs, this can be done in time t(|z|), we call the classification problem solvable in time t(n).


In last week's talk, Martin Ziegler asked the following question: Is there a classification problem (X,Y,Z) which is solvable in double exponential time but not in exponential time and which can be split into two subproblems solvable in exponential time but not in polynomial time?
In this talk we will give the answer.

11. Dezember

 

       

Das Post'sche Problem

 
Ich werde meine Diplomarbeit über das Post'sche Problem vorstellen. Es geht um die Frage, ob es rekursiv aufzählbare Mengen gibt, die weder entscheidbar noch Turing-vollständig sind. Emil Post selbst gelang es nicht, dieses Problem zu lösen, jedoch wurden inzwischen einige Lösungen gefunden. Sie basieren teilweise auf ähnlichen, aber größtenteils auf ganz unterschiedlichen Konzepten. In meinem Vortrag werden die relevantesten dieser Lösungen vorgestellt.
 
 
22. Januar 
 

Die in der Berechenbarkeitstheorie betrachtete Turingreduzierbarkeit kann so aufgefasst werden, dass eine Menge A auf einen Menge B reduzierbar ist, falls alle Funktionen, die mit Orakel A, d.h. mittels Zugriff auf A, berechnet werden können, auch mit Orakel B berechnet werden können. Alternativ kann man Mengen auch hinsichtlich der Größe der Funktionen und partiellen Funktionen vergleichen, die mit der gegebenen Mengen als Orakel berechnet werden können. Im Vortrag wird zunächst diskutiert, welche Reduzierbarkeiten dieses Typs möglich sind. Speziell wird dann die Variante betrachtet, bei der eine Menge A reduzierbar auf eine Menge B ist, falls zu jeder mit Orakel A partiell berechenbaren Funktion eine größere, mit Orakel B partiell berechenbare Funktion existiert. Diese Reduzierbarkeit stimmt auf vielen Mengen mit der Turing-Reduzierbarkeit überein und ihre Grade sind gerade die Turinggrade. (Dem Vortrag liegen gemeinsame Arbeiten mit Frank Stephan und Liang Yu zugrunde.)

29. Januar 
 

Aus Gödels erstem Unvollständigkeitssatz folgt unter Annahme der Church-Turing-These, dass es keine effektiv berechenbare Vervollständigung der Peano-Arithmetik gibt. Levin schlägt in seinem Paper "Forbidden Information" eine Erweiterung dieser Aussage vor.


Im Vortrag wird diese Erweiterung und die ihr zugrundeligende Argumentation vorgestellt und kritisch diskutiert werden. Eine zentrale Rolle wird dabei die wechselseitige Information zweier unendlicher Binärfolgen spielen. Der Vortrag ist eine Zusammenfassung meiner Diplomarbeit.

5. Februar

 

 

 

 

 

 

 

 

 

 

 

 

       

Maximal Pairs and Array Noncomputability

 
A pair (A,B) of computably enumerable (c.e.) sets is a maximal pair if there is no c.e. set C such that A and B are identity-bounded Turing reducible to C. Ambos-Spies, Ding, Fan and Merkle (2012) have characterized the Turing degrees of (the halves of) maximal pairs in terms of array noncomputability (a.n.c.) by showing that a c.e. Turing degree contains a c.e. set A which is half of a maximal pair if and only if this degree contains a maximal pair (A,B) if and only if this degree is a.n.c. In our talk we give a new proof of this theorem which shows that the corresponding (and stronger) result for weak truth table degrees is true too.