The Gamma question for many-one degrees

• Published in: Annals of pure and applied logic 2017-07, Vol.168 (7), p.1396-1405
• Main Author: Harrison-Trainor, Matthew
• Format: Article
• Language: English
• Subjects: Coarse computability; Computability theory; Gamma question
• ISSN: 0168-0072
• DOI: 10.1016/j.apal.2017.01.006

A set A is coarsely computable with density r∈[0,1] if there is an algorithm for deciding membership in A which always gives a (possibly incorrect) answer, and which gives a correct answer with density at least r. To any Turing degree a we can assign a value ΓT(a): the minimum, over all sets A in a, of the highest density at which A is coarsely computable. The closer ΓT(a) is to 1, the closer a is to being computable. Andrews, Cai, Diamondstone, Jockusch, and Lempp noted that ΓT can take on the values 0, 1/2, and 1, but not any values in strictly between 1/2 and 1. They asked whether the value of ΓT can be strictly between 0 and 1/2. This is the Gamma question. Replacing Turing degrees by many-one degrees, we get an analogous question, and the same arguments show that Γm can take on the values 0, 1/2, and 1, but not any values strictly between 1/2 and 1. We will show that for any r∈[0,1/2], there is an m-degree a with Γm(a)=r. Thus the range of Γm is [0,1/2]∪{1}. Benoit Monin has recently announced a solution to the Gamma question for Turing degrees. Interestingly, his solution gives the opposite answer: the only possible values of ΓT are 0, 1/2, and 1.