To determine whether a given
Turing machine M
halts when given
empty input. Sometimes refers to the variant of testing if M halts on
input x; however, we may
simulate this variant by defining a Turing machine M' which first writes down x, and then simulates the operation of M; M' halts (on empty input) iff M halts on input x. In any case, we shall deal with this variant, but it really makes no difference. You may substitute "
computer program" for "Turing machine" in this description, with no change in the content.
The halting problem is undecideable: there does not exist a Turing machine H such that H(e,x)=1 if e encodes a Turing machine M which halts on input x, and H(e,x)=0 otherwise. Suppose for the sake of contradiction that such a machine H existed. Define a new machine H': H' reads one input x, then calculates H(x,x); if H(x,x)=0 it halts, else H(x,x)=1 and H' goes into an infinite loop. Let f be the encoding of H'. What does H' do on input f? It halts iff H(f,f)=0, which (by the definition of H) occurs iff the machine encoded by f does not halt on input f, i.e. iff H' does not halt on input f. Since H' must either halt on input f or enter an infinite loop (i.e. not halt), this is impossible: H'(f) halts iff it doesn't. Thus no such machine H can exist.