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.)


Die Seite befindet sich im Aufbau

 

Vorträge

18. Oktober 2011, 16 Uhr c.t., HS 134, AM

Thorsten Kräling, Universität Heidelberg
Ein Unterschied der rekursiv aufzählbaren ibT- und cl-Grade


8. November 2011, 16 Uhr c.t., HS 134, AM

Klaus Ambos-Spies, Universität Heidelberg
Simple Sets and Strongly Bounded Turing Reducibilities


15. November 2011, 16 Uhr c.t., HS 134, AM

Wolfgang Merkle, Universität Heidelberg
Zufälligkeit bezüglich endlicher Automaten


13. Dezember 2011, 16 Uhr c.t., HS 134, AM

Klaus Ambos-Spies, Universität Heidelberg
Finite-State Genericity: On the Diagonalization Strength of Finite Automata


31. Januar 2012, 16 Uhr c.t., HS 134, AM

Rupert Hölzl, LIAFA Paris
The Denjoy alternative for computable functions


18. Oktober 2011

Ein Unterschied der rekursiv aufzählbaren ibT- und cl-Grade

Eine Menge A heißt "identity-bounded Turing"(ibT)-reduzierbar auf eine Menge B, falls A auf B Turing-reduzierbar ist und die Orakelfragen bei Eingabe x nicht größer als x sind. Verlangt man lediglich, dass die Orakelfragen bei Eingabe x nicht größer als x+c für eine Konstante c sind, so erhält man den verwandten Begriff der "computable Lipschitz"(cl)-Reduzierbarkeit. Die entsprechenden partiellen Ordnungen der rekursiv aufzählbaren ibT- bzw. cl-Grade teilen viele Eigenschaften, was zu der Frage führt, ob sie womöglich alle (in der Prädikatenlogik erster Stufe beschreibbaren) Eigenschaften teilen, d.h. elementar äquivalent sind.
 
Im Vortrag wird diese Frage gemäß einem Ergebnis von Ambos-Spies, Bodewig, Fan und Kräling negativ beantwortet werden, indem wir untersuchen, wann es zu zwei ibT- bzw. cl-Graden a und b einen Grad c unterhalb von a so gibt, dass a die kleinste obere Schranke von b und c ist.

15. November 2011

Zufälligkeit bezüglich endlicher Automaten

Im Vortrag wird das bekannte Ergebnis von Agafonoff und von Schnorr und Stimm dargestellt, dass die üblichen über Auswahlen oder Wetten definierten  Zufallsbegriffe für unendliche Folgen (aus Nullen und Einsen) bezüglich des Berechnungsmodells endlicher Automaten alle zum Konzept einer normalen Folge äquivalent sind. Eine Folge ist dabei normal, falls für alle Längen n  jedes Wort u der Länge n in der Folge mit der zu erwartenden asymptotischen Häufigkeit 2^{-n} auftritt. Weiter stellen wir Ergebnisse von Merkle und Reimann vor, die zeigen, dass bereits für Berechnungsmodelle, die nur wenig mächtiger sind als endliche Automaten, diese Äquivalenzen nicht mehr gelten. 

31. Januar 2012

The Denjoy alternative for computable functions

The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f: R->R, the Denjoy alternative holds outside a null set, i.e., for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +1, and the limit inferior −1. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the Denjoy-Young-Saks theorem. To answer this question Demuth investigated effective versions of the theorem and proved that Demuth randomness is strong enough to ensure the Denjoy alternative for Markov computable functions. In this paper, we show that the set of these points is indeed strictly bigger than the set of Demuth random reals — showing that Demuth’s sufficient condition was too strong — and moreover is incomparable with Martin-Löf randomness; meaning in particular that it does not correspond to any known set of random reals. To prove these two theorems, we study density-type theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized by the only very recently defined notion of difference randomness. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue nondensity points that are well-behaved in the sense that the “density holes” around the point are continuous intervals whose length follows a certain systematic rule. An essen