Turing degree of some functions related to Rice's theorem

Question

Rice's theorem asserts that as soon as $f$ is non-trivial (i.e., non-constant), and extensional (i.e., $f(M) = f(M')$ as soon as $M$ and $M'$ are codes of Turing machines with the same behavior, in the sense that both halt and return the same output or both don't halt), $f$ is uncomputable.

One classic way to prove this is by reduction from the halting problem. The key observation is that all machines that don't terminate are sent by $f$ to the same value (by extensionality), and there is a Turing machine $P$ such that $P(f)$ is a different value (by non-triviality). The reduction takes a Turing machine $M$ and builds a machine $E$ that runs $M$ and ignores the output, then runs $P$ and returns the output. One sees that $E$ has the same behavior as machines that don't halt, or the same behavior as $P$, depending on the termination of $M$, thus the value of $f$ on $E$ allows to decide the termination of $M$.

I'm interested in [edit: total] functions $f$ that verify a weaker condition:

• If $M$ is (the code of) a Turing machine that halts and returns 0, then $f(M) = 0$,
• If $M$ is a Turing machine that halts and returns 1, then $f(M) = 1$.

There is no guarantee on the value of $f(M)$ if $M$ doesn't terminate, or if it terminates but returns a value other than 0 or 1.

The motivation is a riddle proposed by David Madore (see http://www.madore.org/~david/weblog/d.2023-12-24.2774.dragon-riddle.html in French).

I am able to prove that such a function $f$ is uncomputable, by a diagonalization argument: assuming it is computed by a Turing machine $F$, use Kleene's recursion theorem to build the program

$E : \text{if}\ F(E) = 0\ \text{then return}\ 1\ \text{else return}\ 0$

Since $F$ halts, $E$ halts and returns 0 or 1. Either way, we get a contradiction.

However, the proof of Rice's theorem by reduction actually gives a slightly stronger statement than "$f$ is uncomputable": it also proves that the halting problem is reducible to $f$, or in other words, the Turing degree of $f$ is $≥ 0'$. I could not find a similar proof with the weakened assumption.

Question: Is it true that any function $f$ verifying this weaker assumption has Turing degree $≥ 0'$?

Answer 1

Just to clarify the question, you are demanding that $f$ be total, i.e. that $f(M)$ terminate in all cases, even if $M$ does not terminate (otherwise we can simply run $M$ and return its output).

Relation to another question: This being said, question turns out to be the same as the one I asked here on MathOverflow about Turing degrees of sets separating theorems and negations-of-theorems (of Peano arithmetic), i.e., I was asking about a function that must return $1$ on a theorem, $0$ on a negation-of-theorem, and can return anything on undecidable statements (or indeed non-well-formed ones, but that's not interesting because well-formedness is trivially decidable anyway). Allowing it to return anything other than $0$ or $1$ is obviously irrelevant because we can always convert any other answer to $0$ (say).

The reasons why the question you ask (about terminating of Turing Machines) and the one I asked (about separating theorems and negations-of-theorems) are equivalent is that we can convert a machine $M$ to the ($\Sigma_1$) arithmetical statement “$M$ halts and returns $1$”, which is a theorem (of Peano arithmetic) if indeed $M$ halts and returns $1$ and its negation is a theorem (of Peano arithmetic) if $M$ halts and returns $0$; and conversely, we can convert a statement $\varphi$ (of arithmetic) to the Turing machine which searches for proofs of $\varphi$ and $\neg\varphi$ in parallel and returns $1$ if the former is found and $0$ if the latter is found.

The answer proper: Now the quick answer I received is that $f$ is not necessarily of degree $\geq\mathbf{0}'$, indeed it can be of low degree (that is $\deg(f)' = \mathbf{0}'$, which clearly implies $\deg(f) \not\geq \mathbf{0}'$) as follows from Jockush-Soare low basis theorem which states that every infinite computable subtree of the infinite binary tree $\lbrace 0,1\rbrace^*$ has a low infinite branch. (See, e.g., Cooper, Computability Theory (2004), theorem 15.4.3, or Soare, Turing Computability and Applications (2016), theorem 3.7.2, for proof and further explanations.)

So in the context of your question, you would do this: enumerate all Turing Machines in a sequence $(M_n)$ and then define a binary subtree $\mathscr{T}$ of $\lbrace 0,1\rbrace^*$ as follows: to decide whether a length $n$ binary word $w$ is part of $\mathscr{T}$, you run $M_0,\ldots,M_{n-1}$ for $n$ steps: if $M_i$ terminates during that time and returned $0$ or $1$, then the $i$-th letter of $w$ must equal that result (otherwise, the $i$-th letter of $w$ has no constraint). Clearly this is decidable, and clearly this is a tree (as constraints are only ever added); it is sometimes known as the (a?) Kleene tree. Now given an infinite branch of the tree, seen as an infinite binary word, we simply let $f$ on $M_n$ return the $n$-th letter of that word: this satisfies your constraints, because if $M_n$ terminates after $k\geq n$ steps, then no word of length $k$ in $\mathscr{T}$ will have an $n$-th letter that disagrees with the output of $M_n$, and in particular the infinite branch cannot have made that choice. So by the low basis theorem, there is an $f$ of low degree.

Further remarks: From Laurent Bienvenu's answer on MathOverflow, we also learn that the possible degrees of functions $f$ as you defined are known as PA degrees and that a number of things are known about them.

I guess this example disproves the common wisdom that proving uncomputability of something (already known to be computably enumerable) is always done by reducing the Halting Problem to that something (wisdom “justified” by the difficulty of exhibiting a natural degree intermediate between $\mathbf{0}$ and $\mathbf{0}'$, especially a c.e. one, a problem solved by the Friedberg-Mučnik theorem). The thing is that here $f$ is unconstrained at many values, so we're not defining a single degree but a class of them.

Note that in some generalizations of Turing degrees (I like to refer to Kihara's paper “Lawvere-Tierney topologies for computability theorists”, which I tried to give an account of on my blog (in French) and which generalizes Turing degrees in various ways up to Lawvere-Tieney topologies on the effective topos), we can define degrees for nondeterministic functions like this, and then we do have a natural intermediate degree between $\mathbf{0}$ and $\mathbf{0}'$, namely the one you defined (if we just say that $f$ is a nondeterministic function returning $0$ and $1$ when $M$ does not terminate returning $0$ or $1$), and is (equivalent to the one) called $\mathtt{LLPO}$ in Kihara's aforementioned paper (because of its relation to a principle of constructive mathematics).