Strong minimal pair problem

Abstract: This talk is about recursively enumerable (r.e.) Turing degrees. We say that two nonzero r.e. degrees a and b form a strong minimal pair, if a ∧ b = 0 and for any nonzero r.e. degree x ≤ a, b ∨ x ≥ a. Joint with Mingzhong Cai, Yiqun Liu, Yong Liu, and Cheng Peng, we are able to show the nonexistence of such a pair. I will not make any attempt to outline the proof. Instead, I plan to talk about our result in relation to earlier ones in the literature, and mention a few interesting (or strange) features of the construction. For instance, the construction is highly nonuniform, we have to prepare three different (families of) sets and one of them will win. Furthermore, the index of the winning set can only be found using 0^(4). I will also make some comments about the priority methods in general and raise some questions hoping to hear suggestions from the audiences.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.