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
|
18. Oktober 2011, 16 Uhr c.t., HS 134, AM Thorsten Kräling, Universität Heidelberg |
|
| |
8. November 2011, 16 Uhr c.t., HS 134, AM Klaus Ambos-Spies, Universität Heidelberg |
| |
15. November 2011, 16 Uhr c.t., HS 134, AM Wolfgang Merkle, Universität Heidelberg |
| |
13. Dezember 2011, 16 Uhr c.t., HS 134, AM Klaus Ambos-Spies, Universität Heidelberg |
| |
31. Januar 2012, 16 Uhr c.t., HS 134, AM Rupert Hölzl, LIAFA Paris |
| |
|
| 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. |
| 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 essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random. |
