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 2014/2015

8. Oktober 2014
Assylbek Issakhov, Al-Farabi Kazhak National University
Computable numberings


21. Oktober 2014 und
11. November 2014
Martin Monath, Universität Heidelberg
On the Density of uniformly bounded c.e. Turing degrees


3. November 2014
Assylbek Issakhov, Al-Farabi Kazhak National University
Computable numberings


18. November 2014
Liang Yu, Nanjing University, China
On those reals which can be random


2. Dezember 2014
Nadine Losert, Universität Heidelberg
Join and meet preservation


9. Dezember 2014
Nan Fang, Peking University
Solovay functions and no-gap phenomena


16. Dezember 2014
Rupert Hölzl, National University of Singapore
Universality, optimality, and randomness deficiency


27. Januar 2015
Li Wei, Kurt Gödel Research Center for Mathematical Logic, Wien
Reverse Model Theory



21. Oktober
11. November

On the Density of uniformly bounded c.e. Turing degrees

 
Recently, Ambos-Spies considered a special type of Turing-reductions, 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 computable-Lipschitz 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 ubT-reductions.


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. r-degrees 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 no-gap phenomena

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



16. Dezember

Universality, optimality, and randomness deficiency
(Joint work with Paul Shafer)

 
A Martin-Löf test U is universal if it captures all non-Martin-Löf random sequences, and it is optimal if for every Martin-Löf test V there is a constant c such that for all n the set Vn+c is contained Un.
We study the computational differences between universal and optimal Martin-Lö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 Martin-Lö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 \omega-categorical theories with related definitions and principles. This is a joint work with Fokina and Turetsky in Kurt G\"{o}del Institute .