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.)
25. Oktober 2016 08. November 2016 10. November 2016 15. November 2016 22. November 2016 29. November 2016 06. Dezember 2016 13. Dezember 2016 20. Dezember 2016 17. Januar 2017 31. Januar 2017 07. Februar 2017
 
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 firstorder 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 WeihrauchVerbandes
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 LevinSchnorr theorem, a sequence X ∈ 2^{ω} is MartinLo ̈f random with respect to the Lebesgue measure if and only if K(X ↾ n) ≥ n − O(1) for every n, where K denotes prefixfree Kolmogorov complexity. Roughly, this means that the MartinLo ̈f random sequences are precisely those sequences with high initial segment complexity. It is wellknown that the LevinSchnorr 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 slowgrowing 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.
