Hauptseminar Mathematische Logik und Theoretische Informatik

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


 

Vorträge im WS 2016/2017

25. Oktober 2016
Klaus Ambos-Spies, Universität Heidelberg
Array noncomputability: a survey and open problems


08. November 2016
Klaus Ambos-Spies, Universität Heidelberg
Descriptive Complexity of Arithmetic Complexity Classes




10. November 2016
Heribert Vollmer, Universität Hannover
Descriptive Complexity of Arithmetic Complexity Classes




15. November 2016
Nadine Losert, Universität Heidelberg
Universally a.n.c. sets (Part I)




22. November 2016
Nadine Losert, Universität Heidelberg
Universally a.n.c. sets (Part II)




29. November 2016
Martin Monath, Universität Heidelberg
Completely a.n.c. degrees




06. Dezember 2016
Klaus Ambos-Spies, Universität Heidelberg
Maximal Pairs and Array Noncomputability




13. Dezember 2016
Ivan Titov, Universität Heidelberg
Strukturelle Eigenschaften des Weihrauch-Verbandes




20. Dezember 2016
Rupert Hölzl, Universität der Bundeswehr München
Randomness for computable measures and initial segment complexity




17. Januar 2017
Ivan Titov, Universität Heidelberg
Strukturelle Eigenschaften des Weihrauch-Verbandes (Teil II)




31. Januar 2017
Martin Monath, Universität Heidelberg
C.e. high Turing degrees contain c.e. array computable weak truth table degrees




07. Februar 2017
Klaus Ambos-Spies, Universität Heidelberg
Some observations on mitotic sets




 


25. Oktober 2016

Learnability of finite variants of a single language and autoreducibility

 
Let $S^+_L$ and $S^-_L$ be the families of languages obtained from the language $L$ by adding to $L$ respectively omitting from $L$ at most one element. By characterizing the languages $L$ for which these families are learnable, we separate the following six major learnability criteria: TxtFin, TxtEx, TxtBC, InfFin, InfEx, and InfBC, where the first three criteria are finitary/explanatory/behaviourly correct learning from text while the last three criteria are the corresponding criteria for learning from informant. In case of the criterion InfEx, $S^+_L$ can be learnt iff the language $L$ is autoreducible.



 



10. November 2016

Descriptive Complexity of Arithmetic Complexity Classes

 
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulas. We completely determine the inclusion structure and show that #P and #AC0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P.



 



13. Dezember 2016

und

17. Januar 2017

Strukturelle Eigenschaften des Weihrauch-Verbandes

 
In the present thesis we address the issue of the Weihrauch reducibility. In addition to the Weihrauch lattice we introduce the parallel and the finite parallel Weihrauch lattice, into all of which the Medvedev lattice can be embedded. We particularly focus on the embedding of the Medvedev lattice into the parallel Weihrauch lattice and describe it more accurately than previous publications. We also prove that the Weihrauch degree of the weak König's lemma (WKL) is significantly smaller than the Weihrauch degree of the König's lemma (KL) and is equal to the Weihrauch degree of the parallelized lesser limited omniscience principle (LLPO).



 



20. Dezember 2016

Randomness for computable measures and initial segment complexity

 
According to the Levin-Schnorr theorem, a sequence X ∈ 2ω is Martin-Lo ̈f random with respect to the Lebesgue measure if and only if K(X ↾ n) ≥ n − O(1) for every n, where K denotes prefix-free Kolmogorov complexity. Roughly, this means that the Martin-Lo ̈f random sequences are precisely those sequences with high initial segment complexity. It is well-known that the Levin-Schnorr theorem can be extended to proper sequences, that is, sequences that are random with respect to some computable measure on 2ω . However, in this more general setting the initial segment complexity of sequences that are random with respect to different computable measures can vary widely. We study the various growth rates of proper sequences. In particular, we show the initial segment complexity of a proper sequence X is bounded from below by a computable function if and only if X is random with respect to some computable, continuous measure. We also identify a global computable lower bound for the initial segment complexity of all μ-random sequences for a computable, continuous measure μ. Furthermore we show that there are proper sequences with extremely slow-growing initial segment complexity, i.e., there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. Lastly, we prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on 2ω, namely diminutive measures and trivial measures.