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.)
11. Oktober 2013
29. Oktober 2013 und 12. November 2013 18. November 2013 21. November 2013 26. November 2013 3. Dezember 2013 10. Dezember 2013
 
11. Oktober 
Lebesgue density and Ktriviality
Suppose that a computably enumerable set A is Turing below a random set that does not compute the halting problem. Then A is Ktrivial by work dating from 2004 [1]. Stephan then asked whether the converse holds: is every c.e. Ktrivial below an incomplete random? This question became known as the covering problem, and took eight years to be answered in the affirmative.
The proof combines results of two teams of researchers: Bienvenu, Greenberg, Kucera, Nies, and Turetsky form one team; Day and Miller the second. Unexpectedly, the answer involved the notion of density from analysis. The first team showed that if a random real fails the Lebesgue density theorem for effectively closed sets, then it computes all the Ktrivials. The second team used forcing to provide a random real of this kind that is Turing incomplete. The strongest affirmative answer to the covering problem is that some incomplete random ∆2 set computed all the Ktrivials. An overview is given in [2].
After explaining the proof, we consider the random reals for which the effective Lebesgue density theorem holds. They form an interesting class, with several analytical characterisations, and an analog in higher randomness.
[1] D. Hirschfeldt, A. Nies, and F. Stephan. Using random sets as oracles. Journal of the London Mathe matical Society 75 (2007) 610 – 622. [2] L. Bienvenu, A. Day, N. Greenberg, A. Kucera, J. Miller, A. Nies, and D. Turetsky. Computing Ktrivial sets by incomplete random sets. Research announcement, to appear in Bull. Symbolic Logic. 
29. Oktober 
Bounded Turing Reducibilities
In den 2 Sitzungen des Hauptseminars Mathematische Logik und Theoretische Informatik am 29.10. und 5.11.2013 trifft sich der Arbeitskreis "Bounded Turing Reducibilities" und diskutiert neuere Ergebnisse und offene Probleme über die stark bzw. uniform beschränkten TuringReduzierbarkeiten. Interessenten sind hierzu herzlich eingeladen. In der Sitzung am 29.10. wird eine kurze Einführung in die Thematik gegeben. Die Themen sind so gewählt, dass keine über die Einführung hinausgehenden Spezialkenntnisse erforderlich sind und gute Grundkenntnisse der Berechenbarkeitstheorie ausreichen.

12. November 
Some betting games and prediction of compressible sequences
Key words: Monotonic, nonmonotonic, sequenceset and generalized betting in relation to MartinLöf Randomness

18. November 
Effectively closed classes, negligibility, and depth
In this talk, I will introduce the notions of negligible and deep effective closed subclasses of Cantor space. Intuitively, an effectively closed class C is negligible if there is no probabilistic algorithm (i.e. a Turing functional equipped with a random oracle) that can compute a member of C with positive probability. Similarly, an effectively closed class C is deep if there is no probabilistic algorithm that can compute an initial segment of a member with sufficiently high probability (in a sense that I will make precise). After discussing some basic properties of negligible and deep classes, I will provide some examples, most notably, the collection of consistent completions of Peano arithmetic. This is joint work with Laurent Bienvenu and Antoine Taveneaux.

21. November 
Randomness in the Weihrauch degrees
The Weihrauch degrees are a degree structure that can be used to classify how complex it is to find solutions to certain mathematical tasks, that typically arise from classical mathematical theorems, for example in analysis. We will give an overview over recent work about interactions between these degrees and the field of algorithmic randomness. In particular we will discuss where two different models of randomized computation are located in this lattice: computation with access to a MartinLo ̈f random oracles and computation with a Las Vegas algorithm. We will see that these two models can be separated in the Weihrauch degree, which is in contrast to results in the related field of reverse maths, where they are known to coincide. After briefly discussing some other results relating the two subjects mentioned above, we present some open questions.

26. November 
Nonc.e. ibTdegrees inside c.e. cldegrees
We show that, for some but not all noncomputable c.e. sets A, the cldegree of A contains a nonc.e. ibTdegree. Moreover we discuss possible extensions of these results to the other bounded Turing reducibilties.

3. Dezember 
Computable numberings of the families of total functions in the arithmetical hierarchy
A numbering ν : ω → F of a family of unary computable functions is called com
putable if the binary function ν(n)(x) is computable, [1]. A Friedberg numbering of a family is just a computable onetoone numbering. It is wellknown that the Rogers semilattice of a computable family F either consists of one element or is infinite, [1]; and that, in the nontrivial case, it is never a lattice and has no maximal elements; and contains either one or infinitely many minimal elements, [2].
We generalize the notion of computable numbering for the families of functions in the arithmetical hierarchy following [3]. Let F be a family of total unary functions from Σ0n+1,n ∈ ω. A numbering ν : ω → F is called Σ0n+1computable if the binary function ν(n)(x) is computable relative to the oracle ∅(n) [3].
Theorem 1. Let F ⊆ Σ0n+2 be an infinite Σ0n+2computable family of total functions. Then F has infinitely many pairwise nonequivalent Friedberg numberings.
Theorem 2. There are a family F and Σ0n+2computable numbering α of the family F such that no Friedberg numbering of F is reducible to α.
This is a solution to Question 2, [4]: Theorem 3. If F contains at least two functions, then F has no principal Σ0n+2
computable numbering.
[1] Yu. L. Ershov, Theory of numberings, Nauka, Moscow, 1977 (in Russian). [2] S. S. Marchenkov, The computable enumerations of families of general recur sive functions, Algebra and Logic, vol. 11 (1972), no. 5, pp. 326–336. [3] S. A. Badaev and S. S. Goncharov, Rogers semilattices of families of arith metic sets, Algebra and Logic, vol. 40 (2001), no. 5, pp. 283–291. [4] S. A. Badaev and S. S. Goncharov, The theory of numberings: Open prob lems, Contemporary Mathematics (University of Colorado, Boulder), (Peter A. Cholak, Steffen Lempp, Manuel Lerman and Richard A. Shore, editors), vol. 257, American Mathematical Society, 2000, pp. 23–38. 
10. Dezember 
Generalized universal numberings
I will give a talk on the most important numberings for the families of sets which can be uniformly enumerated relative to a given arbitrary oracle.
