Complexity_ A Guided Tour - Melanie Mitchell [32]
Turing first assumed that the answer is “yes,” that is, there is always a definite procedure that can decide whether or not a given statement is true. Turing then proposed the following statement:
Turing Statement: Turing machine M, given input I, will reach the halt state after a finite number of time steps.
By the first assumption, there is some definite procedure that, given M and I as input, will decide whether or not this particular statement is true. Turing’s proof shows that this assumption leads to a contradiction.
It is important to note that there are some Turing machines that never reach the halt state. For instance, consider a Turing machine similar to the one in our example above but with only two rules:
If you are in the start state and read a 0 or a 1, change to the even state and move one cell to the right.
If you are in the even state and read a 0 or a 1, change to the start state and move one cell to the left.
This is a perfectly valid Turing machine, but it is one that will never halt. In modern language we would describe its action as an “infinite loop”—behavior that is usually the result of a programming bug. Infinite loops don’t have to be so obvious; in fact, there are many very subtle ways to create an infinite loop, whose presence is then very hard to detect.
Our assumption that there is a definite procedure that will decide the Turing Statement is equivalent to saying that we can design a Turing machine that is an infinite loop detector.
More specifically, our assumption says that we can design a Turing machine H that, given the code for any machine M and any input I on its tape, will, in finite time, answer “yes” if M would halt on input I, and “no” if M would go into an infinite loop and never halt.
The problem of designing H is called the “Halting problem.” Note that H itself must always halt with either a “yes” or “no” answer. So H can’t simply run M on I, since there would be some possibility that M (and thus H) would never halt. H has to do its job in some less straightforward way.
It’s not immediately clear how it would work, but nonetheless we have assumed that our desired H exists. Let’s denote H(M, I) as the action of running H on input M and I. The output is “yes” (e.g., a single 1 on the tape) if M would halt on I and “no” (e.g., a single 0 on the tape) if M would not halt on I.
Now, said Turing, we create a modified version of H, called H’, that takes as input the code for some Turing machine M, and calculates H(M, M). That is, H’ performs the same steps that H would to determine whether M would halt on its own code M. However, make H’ different from H in what it does after obtaining a “yes” or a “no”. H just halts, with the answer on its tape. H’ halts only if the answer is “No, M does not halt on code M.” If the answer is “Yes, M does halt on code M,” H’ goes into an infinite loop and never halts.
Whew, this might be getting a bit confusing. I hope you are following me so far. This is the point in every Theory of Computation course at which students either throw up their hands and say “I can’t get my mind around this stuff!” or clap their hands and say “I love this stuff!”
Needless to say, I was the second kind of student, even though I shared the confusion of the first kind of student. Maybe you are the same. So take a deep breath, and let’s go on.
Now for Turing’s big question:
What does H’ do when given as input the code for H’ , namely, its own code? Does it halt?
At this point, even the second kind of student starts to get a headache. This is really hard to get your head around. But let’s try anyway.
First, suppose that H’ does not halt on input H’. But then we have a problem. Recall that H’, given as input the code for some Turing machine M, goes into an infinite loop if and only if M does halt on M. So