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.
- 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 ∅'.
- 25/01/2012, 17:00 hrs, Week 3.
Chinese New Year.
- 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.
- 15/02/2012, 17:00 hrs, Week 6.
Mars Yamaleev.
- 29/02/2012, 17:00 hrs, Week 7.
Cheng Yong.
- 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.
- 14/03/2012, 17:00 hrs, Week 9.
Alexander Melnikov.
- 21/03/2012, 17:00 hrs, Week 10.
Li Wei.
- 28/03/2012, 17:00 hrs, Week 11.
Yang Yue.
- 04/04/2012, 17:00hrs, Week 12.
Wu Guohua.
- 11/14/2012, 17:00hrs, Week 13.
Gao Ziyuan.
Talks from the
previous semesters.