# 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 SS 2015 14. April 2015 14:15h, Raum -101 Liang Yu, Nanjing University Definability in the computably enumerable degrees 21. April 2015 Xizhong Zheng, Arcadia University, Pennsylvania, USA Computable Curves 19. Mai 2015 Rupert Hölzl, Universität Heidelberg The reverse mathematics of inductive inference 28. Mai 2015 Laurent Bienvenu, University of Paris 7 Probabilistic algorithms in computability theory 2. Juni 2015 Alexander Shen, LIRMM Montpellier Forbidden strings, complexity arguments and tetris 7. Juli 2015 14:15h, INF 368 (IWR), SR 432 Bora I. Kumova, Izmir Insititute of Technology The Ancient Syllogistic System and Its Properties 7. Juli 2015 Yizheng Zhu, Universität Münster The Higher Sharp 8. Juli 2015 16:15h, INF 248 (IfI), SR 015 Bora I. Kumova, Izmir Insititute of Technology Fuzzy-Syllogistic Systems and Their Applications for Approximate Reasoning 14. Juli 2015 Xishun Zhao, University at Guangzhou Recent Results on Minimal Unsatisfiability 15. Juli 2015 11:15h Victor Selivanov, Institute of Informatics Systems, Novosibirsk On Weihrauch degrees of k-partitions of the Baire space 19. Mai The reverse mathematics of inductive inference   (Joint work with F. Stephan and S. Jain.) It is a widespread intuition among mathematicians to think of certain theorems as stronger or weaker versions of other theorems. Of course, strictly speaking, all true theorems are logically equivalent, so at first sight it might not be obvious how one would go about formalizing this intuition. In the 1970’s, Friedman proposed a way of making this formalization and thereby inspired a new way to look at mathematics. He suggested to study classical mathematical theorems and their relations by analysing how they mutually imply each other over weak logical systems. Over such systems it then becomes meaningful to discuss whether theorems are equivalent, imply each other, and so on. This approach has been used to study and classify theorems from many areas of mathematics. In this talk, we will discuss recent work that applies the reverse mathematics method to the field of Inductive Inference. This field deals with the ability of machines or algorithms to learn objects when provided with partial information about these objects. We will look at a number of classical results in this area, in particular results by Angluin, and analyse them using the methodology of reverse mathematics. In particular we will identify three different weak logical systems and study in what situations, depending on the different learning environments, they are sufficient to permit learning, and in what situations they are not. 28. Mai Probabilistic algorithms in computability theory   Since the Friedberg-Muchnik solution of Post's problem via injury argument, computability theory has seen the development of very intricate techniques, known as 'priority constructions'. These are effective constructions, therefore they can been seen as algorithms. All these algorithms are deterministic, and there are indeed very few examples of probabilistic algorithms in computability theory. Nevertheless, there is a notable family of such algorithms, discovered by Kautz (reformulated as an explicit probabilistic algorithm is due to Gacs and Shen), which we call 'fireworks arguments'. I will present the basic algorithm to prove Kautz's theorem that every 2-random real computes a 1-generic real. If time permits, I will discuss the improvement of this theorem by Barmpalias, Day and Lewis, and the further still improvement by Bienvenu and Porter. 2. Juni Forbidden strings, complexity arguments and tetris   Assume that for every $k$ some $F_k$ strings of length $k$ are declared "forbidden". If the numbers $F_k$ are small enough, one can guarantee the existence of an infinite sequence that does not contain forbidden factors. Some specific sufficient condition (when $F_k$ are small enough) was suggested by Joe Miller: $\sum_{k\ge 2}^\infty F_k c^k < 2c - 1$ for some $c\in (1/2,1)$. This result can be then used to show the existence of everywhere complex strings ("Levin's lemma") instead of complexity arguments or Lovasz local lemma. Recently P.Ochem, D.Goncalvez and others found a nice proof of Miller's results that uses complexity argument: imagine that bits are added one my one and forbidden strings are canceled (like in tetris game). One can show that if the resulting sequence does not grow, then the string of bits used for the construction is compressible. We present a simplified version of their argument based on amortized analysis. 7. Juli The Ancient Syllogistic System and Its Properties   Traditional categorical syllogism consist of 256 moods in total, 64 moods per figure. Out of them only 24 moods, 6 per figure, are well known to be the only true ones, whereas the remaining 232 are assumed to be false. A systematic analysis of the syllogisms with modern mathematics, like set-theory, algorithms and fuzzy logic, allows us not only to confirm the truth of the 24 moods, but reveals the truth of a 25th mood in the 4th figure to be true too. Furthermore, with two new concepts, the syllogistic cases and the truth ratio, we can calculate a unique truth ratio for every mood, which is in the range [0,1]. It is actually these novel concepts that help revealing the most significant properties of the syllogistic system S, like point symmetric truth of moods, partial overlapping value ranges, equivalence of moods, almost or more true/false moods. The objective of this talk is, to introduce to this modern approach of analysing syllogisms. 7. Juli The Higher Sharp   Assuming Projective Determinacy, the Turing jump and hyperjump operators have their higher level analog, known as the sharp operator and the M_n^\# operator. They are transcendental objects of L or canonical inner models with Woodin cardinals. We give a characterization of these operators in terms of descriptive set theory. This alternative characterization has the advantage of directly generalizing the form the Turing jump and hyperjump operators. It is the cornerstone of generalizing results from descriptive set theory and higher recursion theory up to the projective levels. 8. Juli Fuzzy-Syllogistic Systems and Their Applications for Approximate Reasoning   Using the concepts syllogistic case, truth ratio and fuzzy quantifiers, we generalise the traditional syllogistic system S with two affirmative and two negative quantifiers, of which the existential quantifiers are inclusive, to n fuzzy-syllogistic systems nS with 11) of the Baire space whose components are finite boolean combinations of open sets. In this talk we discuss extensions of these characterizations to as large initial segments of the Weihrauch degree structures as possible.