Logic Seminar in Semester II AY 2011/2012

Talks are Wednesday afternoon in Seminar Room S17#05-11 and start at 17:00 hrs. Here an overview over the topics.
  1. 18/01/2012, 17:00 hrs, Week 2.
    Ng Keng Meng. Jump Inversion and strong reducibilities.
    The study of strong reducibilities has been a major part of computability for a long time. As is well known, tabular reducibilies such as weak truth table (wtt-) and truth table (tt-) reduciblities place restrictions on oracle access. In recent times, truth table reducibility has become a central area of interest as it has been shown to be a natural reducibility to study in algorithmic randomness.
    Recent work by Anderson analyzing an old result of Mohrherr renewed interest in the variations of the classical jump inversion theorems, particularly their connection with the strong reducibilities. We prove that the analogs of Shoenfield's and Sacks' jump inversion results fail when considering tt- and wtt-reducibilities, and in fact they fail in more or less the strongest way that they can. One of our main results show that for any computable sequence of Δ02 sets V0, V1, ..., there exists a Δ02 set S truth-table above ∅' such that for every e, Ve' is not wtt-equivalent to S.
    We also examine the role of strong tabular reducibilities in the completion of pseudojump operators. We show that there is a pseudojump operator V such that VX is Turing above X for every X, and there is no c.e. set A such that VA is wtt-equivalent to ∅'.

  2. 25/01/2012, 17:00 hrs, Week 3.
    Chinese New Year.

  3. 01/02/2012, 17:00 hrs, Week 4.
    Chong Chitat. The strength of Ramsey's Theorem for Pairs.
    Abstract: We discuss the first order strength of Ramsey's Theorem foe pairs RT22 as well as some combinatorial principles weaker than RT22. We also consider SRT22 the stable Ramsey's Theorem for pairs and it's first order strength. We conclude with a theorem on the strength of SRT22 and give a very brief sketch of the proof.
    This is joint work with Ted Slaman and Yang Yue that began in July 2005.

  4. 15/02/2012, 17:00 hrs, Week 6.
    Mars Yamaleev.

  5. 29/02/2012, 17:00 hrs, Week 7.
    Cheng Yong.

  6. 07/03/2012, 17:00 hrs, Week 8.
    Frank Stephan. Random Sets and Recursive Splittings.
    The starting point of this talk is the following: Given a set B, is there a random set A such that for each recursive set C either the intersection of A with C or the intersection of A with the complement of C is Turing above B? This question arises naturally from van Lambalgen's Theorem which permits to split many Martin-Loef random sets into halves which are computationally week. The affirmative answer to this question shows that some Martin-Loef random sets cannot be split into two computationally weak halves in a systematic way, but one half preserves always at least the computation power of B.
    For Schnorr randomness, a stronger result is obtained: Every high Turing degree contains a Schnorr random set A such that A is Turing equivalent to the intersection of A and B for any infinite recursive set B.
    If one looks at Turing degrees, one can show that every degree above the one of the halting problem is the join of two Turing incomplete Martin-Loef random sets.
    This is joint work with Ng Keng Meng and Andre Nies.

  7. 14/03/2012, 17:00 hrs, Week 9.
    Alexander Melnikov.

  8. 21/03/2012, 17:00 hrs, Week 10.
    Li Wei.

  9. 28/03/2012, 17:00 hrs, Week 11.
    Yang Yue.

  10. 04/04/2012, 17:00hrs, Week 12.
    Wu Guohua.

  11. 11/14/2012, 17:00hrs, Week 13.
    Gao Ziyuan.

Talks from the previous semesters.