5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ (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$. $\endgroup$ – Vor Oct 23 '12 at 14:17
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are boolean function and predicate the same concept? If not, I think HALT is a predicate which return 0 or 1. $\endgroup$ – Gigili Oct 26 '12 at 5:43
  • $\begingroup$ @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. $\endgroup$ – Gilles Oct 26 '12 at 10:06
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.