# If a predicate is not computable, what can be said about its negation?

Doing the following exercise:

Let $$\overline{HALT(x,y)}$$ be defined as

$$\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$$

Show that it is not computable.

Just want to make sure I have understood the concept correctly. We had in a theorem that HALT(x,y) is not computable which means that we cannot determine whether program number y eventually halts on input x. I realized that $$\overline {HALT(x,y)}$$ is the negation of HALT(x,y). Is it true (I cannot find it in my book or on the internet) that if a function is (not) computable, its negation is also (not) computable? A function being computable means there is a program p which computes it, we cannot say there is a program Q that computes its negation. Or can we draw such conclusion?

• (to be pendantic) be aware that talking about the "negation" (or complement) of a function is not correct. When you talk about HALT as a function you are talking about the characteristic function of the set $HALT = \{ (M,x) |$ program $M$ halts on $x\}$. And its "negation" is actually the characteristic function of its complement, i.e. $\overline{HALT} = \Sigma^* \setminus HALT$.
– Vor
Oct 23 '12 at 14:17

To answer the literal question that you asked, $\mathsf{HALT}$ is a boolean function, i.e. a function whose values are in the set $\{\mathsf{false}, \mathsf{true}\}$. The negation of $\mathsf{HALT}$ is the composition of this function with the negation operator $\mathsf{not}$. Since $\mathsf{not}$ is bijective, any algorithm that computes $\mathsf{HALT}(x,y)$ terminates if and only if $\mathsf{not}(\mathsf{HALT}(x,y))$ terminates (because if $\mathsf{not}(\mathsf{HALT}(x,y))$ terminates then $\mathsf{not}(\mathsf{not}(\mathsf{HALT}(x,y))) = \mathsf{HALT}(x,y)$ terminates).
Framing the question in a more intuitive manner, $\mathsf{HALT}$ is a predicate: it is the characteristic function of a set. The predicate is computable if and only if the set is decidable, i.e. recursive. The complement of a recursive set is a recursive set (the reasoning above is one way to prove it), which amounts to saying that the negation of the corresponding predicate is computable iff the predicate is.