An NP-Hard Decision Problem:
The Halting Problem

NP - Hard

The halting problem is to determine for an arbitrary deterministic algorithm A and an input I whether algorithm A with input I ever terminates (or enters an infinite loop). It is well known that this problem is undecidable.

The basis of the proof is to suppose that one can determine if a machine will stop on (for our purposes, accept) specific inputs and show that there will always exist a string that no machine can determine (accept). The proof is based on a technique called diagonalization.

From Introduction to Automata Theory, Languages, and Computation, Hopcroft and Ullman, Addison Wesley Publishing Company, Reading Massachusetts, 1979, page 183

Suppose we have a list of ( 0 + 1 )^* in canonical order, where w_i is the ith word, and M_j is the TM whose code is the integer j written in binary. Imagine an infinite table that tells for all i and j whether w_i is in L(M_j). The figure below suggests such a table. 0 means w_i is not in L(M_j) and 1 means it is.

We construct a language L_d by using the diagonal entries of the table to determine membership in L_d. To guarantee that no TM accepts L_d, we insist that w_i is in L_d if and only if the (i, i) entry is 0, that is, if M_i does not accept w_i. Suppose that some TM M_j accepted L_d. Then we are faced with the following contradiction. If w_j is in L_d, then the (j,j) entry is 0, implying that w_j is not in L(M_j) and contradicting L_d = L(M_j). On the other hand, if w_j is not in L_d, then the (j,j) entry is 1, implying that w_j is in L(M_j), which again contradicts L_d = L(M_j). As w_j is either in or not in L_d, we conclude that our assumption, L_d = L(M_j), is false. Thus, no TM in the list accepts L_d and by ( an earlier theorem) no TM whatsoever accepts L_d.