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.
