# 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.

A related property that is not conserved by negation is semi-decidability, as in recursively enumerable sets. The complement of a recursively enumerable set is not r.e. in general (in fact, an r.e. set has an r.e. complement iff it is recursive). Whereas a recursive set's characteristic function uses two values to distinguish between the elements that are in the set and the ones that aren't, a recursively enumerable set can be given as the domain of a partial recursive function: the r.e. set is the domain on which the function has a value. If the function is given as an algorithm, the domain is the part where the computation of the function halts and returns a value; the complement of the domain is the part where the computation does not halt.

• Are boolean function and predicate the same concept? If not, I think HALT is a predicate which return 0 or 1. – Gigili Oct 26 '12 at 5:43
• @Gigili A predicate is a something with a boolean value. A predicate is a boolean-valued function at some level of modeling. Note that in some context, the word predicate might carry the implication that the function is at a particular level, e.g. that it's part of the type language rather than the expression language or things like that. – Gilles 'SO- stop being evil' Oct 26 '12 at 10:06

If a function F is computable, so is !F, as you can simply compute F and return the negated result.

For the same reason, if a function isn't computable, neither is its negation.