No label defined (Q4336988)

This review, and this article, use the terms computable and c.e., which have in the past been called recursive and r.e. The article under review surveys ties between two notions: natural solutions to Post's Problem, and discontinuity. This review will merely define these terms and state some theorems. Let \(A'\) be the halting problem relative to \(A\). Then \(\emptyset'\) is the traditional halting problem. Post (in 1944) asked if there is a c.e. set \(W_e\) such that \(\emptyset <_T W_e <_T \emptyset'\). Actually, he wanted some sort of natural property that would guarantee such a set exists. While there have been many constructions of such sets \(W_e\), one can argue how natural any of them are. One way to pin down the notion of natural is due to Sacks (1967): Is there an index \(e\) such that, for any \(A\) and \(B\), (1) \(A<_T W_e^A <_T A'\) and (2) \(A\equiv_T B\) \(\rightarrow\) \(W_e^A\equiv_T W_e^B\). Slaman and Steel (unpublished) have shown that if we restrict \(A,B\) to be \(\leq_T K\) then such an \(e\) exists. The general problem is still open. Another way to pin down the notion of natural is to ask for an intermediary degree to be definable. A property \(P(x_1,\ldots,x_n)\) of \(n\)-tuples of c.e. Turing degrees is continuous if, whenever it holds at \(a_1,\ldots,a_n\) (all distinct), there exist \(b_1,\ldots,b_n,c_1,\ldots,c_n\) with \(a_i\in (b_i,c_i)\) such that for any \((d_1,\ldots,d_n)\in (b_1,c_1)\times\cdots\times(b_n,c_n)\) \(P(d_1,\ldots,d_n)\) holds. Harrington-Soare showed that any 2-variable, quantifier-free formula is continuous. Stob showed that the property \(P(a,b,c)= a\cup b = c\cup b\) is discontinuous (note that \(\cup\) means join in the Turing degrees). For the entire collection see [Zbl 0859.00022].