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

Question

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?

Answer 1

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.

Answer 2

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.