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.

# Halting problem (thing)

See all of Halting problem, there are 3 more in this node.

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.