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.)
2. November 2010, 16 Uhr c.t., HS 134, AM
Kai Hauser, Technische Universistät Berlin
9. November 2010, 16 Uhr c.t., HS 134, AM
Vadim Puzarenko, Sobolev Institute of Mathematics, Novosibirsk
16. November 2010, 16 Uhr c.t., HS 134, AM
Jason Teutsch, Universität Heidelberg
23. November 2010, 16 Uhr c.t., HS 134, AM
Leonid Levin, Boston University, Universität Heidelberg, Humboldt Foundation
30. November 2010, 16 Uhr c.t., HS 134, AM
Jason Teutsch, Universität Heidelberg
14. Dezember 2010, 16 Uhr c.t., HS 134, AM
Frank Stephan, National University of Singapore
17. Dezember 2010, 13 Uhr c.t., HS - 111, AM
Kai Hauser, TU Berlin
21. Dezember 2010, 16 Uhr c.t., HS 134, AM
Victor Selivanov, Novosibirsk
18. Januar 2011, 16 Uhr c.t., HS 134, AM
Wei Wang, Sun Yat-sen University, Guangzhou
15. Februar 2011, 16 Uhr c.t., HS 134, AM
Chunlai Zhou, Renmin University, Peking
|2. November 2010||
The Axiom of Infinity stipulates the existence of infinite sets. One of the most distinctive and intriguing developments of modern set theory has been the realization that, despite widely divergent incentives for postulating more powerful axioms of infinity, there is essentially only one way of ascending the higher reaches of infinity. To the mathematical realist the unexpected convergence suggests that all these axiomatic extensions describe different aspects of the same underlying reality. That interpretation has come under attack by anti-realists seeking to explain the convergence as an artefact of the language of set theory. Here we show that this reductionist view is flawed by exhibiting examples of arguably natural strong axioms of infinity that are demonstrably incomparable. This is joint work with Hugh Woodin. The talk is self-contained and does not presuppose any particular expertise in mathematical logic.
|9. November 2010||
In this talk we will discuss the following aspects:
|16. November 2010||
In this talk I will demonstrate the power of making (domain-) random strings to be (Kolmogorov-) random. The truth-table degree of the set of shortest programs is a outstanding problem in recursion theory. I will discuss two related sets, the set of shortest descriptions and the set of domain-random strings, whose truth-table degrees depend on the underlying acceptable numbering. It is possible to achieve a priority-free construction of btt-chains and btt-antichains inside the truth-table complete degree by identifying an acceptable set of domain-random strings within each degree.
|23. November 2010||
While fundamental to many sciences, the concept of Randomness is quite paradoxical. Kolmogorov's analysis clarified it greatly by revealing its computational nature.
[See more in Survey: (T.Probab.& Appl. 3/32, 1987) Kolmogorov and Uspenskii. Algorithms and Randomness.]
|30. November 2010||
The classical randomness notions of Schnorr and Kurtz permit gamblers to bet any amount of money within their means. In this talk, we consider a more realistic paradigm in which gamblers must place a minimum bet of one dollar. The corresponding randomness notion turns out to be incomparable with the classical notions mentioned above. Most casinos operate by exploiting the law of large numbers, however, by examining an even more restrictive model in which we ban wagers greater than a million dollars, we obtain an alternate principle through which an online casino might operate profitably. The open questions at the end of this talk should be accessible to a general audience.
|14. Dezember 2010||
Joint Work with: Pavel Semukhin
|17. Dezember 2010||
One very widespread assumption in philosophy has been that empiricism entails materialism: if all knowledge reaches us through our senses, then the only things we can know something about are material objects. We therefore have no basis for believing that there are any non-material objects, and even if there were, we cannot know anything about them. I will examine and develop a view first set forth by the Austrian-German philosopher Edmund Husserl (1859-1938), who argued that there are non-material objects and that they can be recognized in a process very closely related to ordinary perception. In fact, the perception of physical objects is just a special case of this more universal way of recognizing objects of any kind.
|21. Dezember 2010||
We extend the Wagner hierarchy of omega-regular sets to the omega-regular k-partitions, i.e. to k-tuples of pairwise disjoint omega-regular sets exhausting the Cantor space. The notions of CA-reducibility (by continuous functions) and DA-reducibility (by deterministic asynchronous transducers) are extended to k-partitions in a straightforward way. We extend also the notion of Muller acceptor to the notion of Muller k-acceptor in such a way that they recognize precisely the omega-regular k-partitions. Then, using an extension of our fine hierarchy to the fine hierarchy of k-partitions, we extend the main results of K. Wagner to the case of k-partitions. In particular we characterize the structures of CA- and DA-degrees of omega-regular k-partitions up to isomorphism and show that from given two Muller k-acceptors one can compute whether the corresponding omega-regular k-partitions are in the relation CA (or DA).
|18. Januar 2011||
In Reverse Mathematics, people formulate mathematics in second order arithmetic and study strength of theorems with respect to provability or consistency. Among reverse mathematical topics, the strength of Ramsey like combinatorial principles has continuously attracted recursion theorists for decades and some hard questions remain open. In a very recent work, Csima and Mileti presented a new proof of Rainbow Ramsey Theorem for pairs, which is some kind of a dual of Ramsey Theorem for pairs. This new proof is relating to algorithm randomness. Using results in randomness, they proved some interesting reverse mathematical results of Rainbow Ramsey Theorem for pairs. We combine the techniques from Csima-Mileti's work with some early techniques and results relating to Ramsey Theorem for pairs and show that Rainbow Ramsey Theorem for triples is weaker than the Arithmetic Comprehension Axioms.
|15. Februar 2011||
Probability logic has been an important approach to investigate belief types in game-theoretical economics. In this talk, I will first present a probability logic for Harsanyi Type spaces, and show its completeness and unique extension theorem. Next I prove the relative complexity of multi-player interactive epistemology when compared with one-player epistemology by showing that, if the probability indices of the language is restricted to a finite set of rationals, the canonical space for probabilistic beliefs with one player is countable while the canonical one with at least two players has the cardinality of the continuum. In the final part of this talk, I generalize the three notions of definability: implicit definability, reducibility and explicit definability in multimodal logic to the setting of logics of probabilistic belief and knowledge, and show that S5-knowledge can be implicitly defined by probabilistic belief but not reduced