Frank Stephan: Computational aspects of the hyperimmune-free degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 15 August 2018, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: Computational aspects of the hyperimmune-free degrees


A set A has hyperimmune-free degree, if every set B
Turing equivalent to A is already truth-table equivalent to A.
Equivalently, one can also say that every function f Turing reducible
to A is majorised by a recursive function.
Starting with a result that there is a recursive tree T
with uncountably many infinite branches such that all of these
have hyperimmune-free degree, the authors (Ng Keng Meng, Frank Stephan,
Yang Yue and Yu Liang) investigated the overall notion of hyperimmune-free
degrees, their jumps and in particular the extent to which one can
strengthen the before-mentioned result. Indeed, one can achieve that
all the infinite branches on the tree T are not only
hyperimmune-free but also jump-traceable, Schnorr trivial and
of either minimal or recursive Turing degree.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.