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.)
14. April 2015 21. April 2015 19. Mai 2015 28. Mai 2015 2. Juni 2015 7. Juli 2015 7. Juli 2015 8. Juli 2015 14. Juli 2015 15. Juli 2015
 
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 FriedbergMuchnik 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 2random real computes a 1generic 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 settheory, 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 
FuzzySyllogistic 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 fuzzysyllogistic systems nS with 1<n affirmative and 1<n negative fuzzy quantifiers, of which all (n1) existential quantifiers are exclusive. The objective of this talk is to introduce to this approach of generalisation of syllogisms and to experimentally show their application in approximate reasoning. For this purpose we discuss the design of a fuzzysyllogistic ontology reasoner that is based on nS.

14. Juli 
Recent Results on Minimal Unsatisfiability
This talk will give an introduction to the recent progress of the project "Structure and Classification of Minimal Unsatifiability". The speaker will introduce new classes of formulas such as prime formulas, 2prime formulas. In addition, some connections between minimal unsatisfiability and elementary number theory will be established. Some open questions and conjectures will be proposed.

15. Juli 
On Weihrauch degrees of kpartitions of the Baire space
In the 1990s Peter Hertling found useful "combinatorial" characterizations of initial segments of the degree structures under Weihrauch reducibilities on kpartitions (for any integer k>1) 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.
