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.)
8. Oktober 2014 21. Oktober 2014 und 3. November 2014 18. November 2014
2. Dezember 2014 9. Dezember 2014 16. Dezember 2014 27. Januar 2015 Li Wei, Kurt Gödel Research Center for Mathematical Logic, Wien Reverse Model Theory
 
21. Oktober 
On the Density of uniformly bounded c.e. Turing degrees
Recently, AmbosSpies considered a special type of Turingreductions, where the use is bounded by some member of a uniformly computable (u.c.) class of functions, the so called uniformly bounded Turing (ubT) reducibilities. In the special case of the computableLipschitz reducibility, where we consider the u.c. class of functions of the form identiy plus some constant, Adam Day could show that the induced partial ordering of c.e. degrees is not dense. In this talk, we will use the ideas Day used in his proof and show, how to spread the result to a wider class of ubTreductions.

18. November 
On those reals which can be random
I will present some recent results on the studying which reals can be (1, \Pi^1_1, or L)random. Then I will give some applications of these results.

2. Dezember 
Join and meet preservation
We will look at reducibilities r and r' such that r is stronger and r' and ask the question whether joins and meets in the c.e. rdegrees are preserved in the c.e. r'degrees. We will give an example where this is not the case for joins.

9. Dezember 
Solovay functions and nogap phenomena
In recent years, Solovay functions have gained some attention since in some cases they can be substitute for prefixcomplexity function K. I will present two more such cases, the characterizations of the notions 2randomness and weakly low for K. Furthermore, we will have a detailed look on the properties of Solovay functions and will analyze nogap phenomena related to these characterizations.

16. Dezember 
Universality, optimality, and randomness deficiency (Joint work with Paul Shafer)
A MartinLöf test U is universal if it captures all nonMartinLöf random sequences, and it is optimal if for every MartinLöf test V there is a constant c such that for all n the set V_{n+c} is contained U_{n}.
We study the computational differences between universal and optimal MartinLöf tests as well as the effects that these differences have on both the notion of layerwise computability and the Weihrauch degree of LAY, the function that produces a bound for a given MartinLöf random sequence’s randomness efficiency. We prove several robustness results concerning the Weihrauch degree of LAY. Along similar lines we also study the principle RD, a variant of LAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAY. 
27. Januar 
Reverse Model Theory
In this project, we investigate the second order strength required to prove theorems in Model Theory. More precisely, we consider characterizations of \omegacategorical theories with related definitions and principles. This is a joint work with Fokina and Turetsky in Kurt G\"{o}del Institute .

