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 im WS 2013

11. Oktober 2013
André Nies, University of Auckland
Lebesgue density and K-triviality

29. Oktober 2013 und
5. November 2013
Sitzung des Arbeitskreises
Bounded Turing Reducibilities

12. November 2013
Tomislav Petrovic, Universität Zagreb
Some betting games and prediction of compressible sequences

18. November 2013
Christopher Porter, Universität Paris
Effectively closed classes, negligibility, and depth

21. November 2013
Rupert Hölzl, Universität der Bundeswehr München
Randomness in the Weihrauch degrees

26. November 2013
Klaus Ambos-Spies, Universität Heidelberg
Non-c.e. ibT-degrees inside c.e. cl-degrees
(Arbeitskreis Bounded Turing Reducibilities)

3. Dezember 2013
Assylbek Issakhov, Al-Farabi Kazhak National University
Computable numberings of the families of total functions in the arithmetical hierarchy

10. Dezember 2013
Serikzhan Badaev, Al-Farabi Kazhak National University
Generalized universal numberings


11. Oktober

Lebesgue density and K-triviality

Suppose that a computably enumerable set A is Turing below a random set that does not compute the halting problem. Then A is K-trivial by work dating from 2004 [1]. Stephan then asked whether the converse holds: is every c.e. K-trivial 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 K-trivials. 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 K-trivials. 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 K-trivial sets by incomplete random sets. Research announcement, to appear in Bull. Symbolic Logic.

29. Oktober
5. November

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 Turing-Reduzierbarkeiten. 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, sequence-set and generalized betting in relation to Martin-Lö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 Martin-Lo ̈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

Non-c.e. ibT-degrees inside c.e. cl-degrees

We show that, for some but not all noncomputable c.e. sets A, the cl-degree of A contains a non-c.e. ibT-degree. 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 one-to-one numbering. It is well-known that the Rogers semilattice of a computable family F either consists of one element or is infinite, [1]; and that, in the non-trivial 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+1-computable if the binary function ν(n)(x) is computable relative to the oracle ∅(n) [3]. Theorem 1. Let F ⊆ Σ0n+2 be an infinite Σ0n+2-computable family of total functions. Then F has infinitely many pairwise non-equivalent Friedberg numberings. Theorem 2. There are a family F and Σ0n+2-computable 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.