Hauptseminar Mathematische Logik und Theoretische Informatik

Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in SR 1 des Gebäudes INF 205.
(The talks are usually on Tuesday at 4 p.m. in SR 1 of building INF 205.)


 

Vorträge im
Sommersemester 2016

10. Mai 2016
Nadine Losert, Universität Heidelberg
Totally omega-C.E. Degrees and Complex Left-C.E. Reals - Part1


24. Mai 2016
Martin Monath, Universität Heidelberg
Totally omega-C.E. Degrees and Complex Left-C.E. Reals - Part2


31. Mai 2016
Nan Fang, Universität Heidelberg
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega


07. Juni 2016
Martin Monath, Universität Heidelberg
On totally omega-c.e. degrees


14. Juni 2016
Martin Monath, Universität Heidelberg 7
On totally omega-c.e. degrees- Part2


12. Juli 2016
Liang Yu, Nanjing University 7
On reals weakly low for K


26. Juli 2016
Max Löhlein, Universität Heidelberg
Anwendung der Inkomprimierbarkeits-Methode in der Laufzeitanalyse


26. Juli 2016
Anja Kaiser, Universität Heidelberg
Charakterisierung K-trivialer Mengen durch Lowness-Eigenschaften


 



31. Mai

Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

 
We characterise the asymptotic upper bounds to use any Omega-like reals to compute arbitrary c.e. reals. We show that the following two conditions are equivalent for any computable function h such that h(n) - n is non-decreasing: (1) h(n) - n is an information content measure, (2) for every c.e. real there exists a Turing functional via which Omega computes it with use bounded by h. In the meanwhile, we get some extended version of the theorem that there are maximal pairs in the cl-degrees among all left-c.e. reals.


07. Juni

On totally omega-c.e. degrees

 
This talk is a summary of the two talks on totally omega-c.e. degrees and complex left-c.e. reals and gives an overview on recent research topics in our work group.


14. Juni

On totally omega-c.e. degrees -Part2

 
This talk is the continuation of the talk on June 07.


12. Juli

On reals weakly low for K

 
Given an finite subset A of numbers, we say that a real x is low for K on A if x does not compress any number in A according to K and a real x is weakly low for K on A up to a constant if x does not compress infinitely many numbers in A. We prove a plenty of results concerning these notions and apply them to investigate the theory of algorithmic randomness.


26. Juli

Anwendung der Inkomprimierbarkeits-Methode in der Laufzeitanalyse

 
Es wird das grundlegende Vorgehen der Inkomprimierbarkeits-Methode zur Laufzeitanalyse vorgestellt und am Beispiel von Quicksort veranschaulicht.


26. Juli

Charakterisierung K-trivialer Mengen durch Lowness-Eigenschaften

 
Dieser Vortrag beschäftigt sich mit einigen Eigenschaften und äquivalenten Charakterisierungen von K-Trivialität. Hierzu werden zunächst relative Zufälligkeit und Kolmogorov-Komplexität eingeführt und die Reduzierungen K, LK und LR betrachtet. Anschließend werden die zugehörigen Lowness-Begriffe untersucht.