chapter
4 Pages

H

Formally, the halting setK0 is the set of codes of pairs of natural numbers (e, x) such that the partial recursive function with Gödel number e is defined on input x; i.e., K0 = {〈e, x〉 : ϕe(x) is defined}, where ϕe is the partial recursive function with Gödel number e. The halting set is not recursive (computable), as a set of natural numbers, although it is recursively (computably) enumerable. Another halting set is K = {e : ϕe(e) is defined}. The set K is also computably (recursively) enumerable but noncomputable (non-recursive).