Programmer's Guide To Theory - The Halting Problem |
Written by Mike James | ||||||
Monday, 16 December 2019 | ||||||
Page 2 of 2
ReductionAs soon as you have one of the flood gates open and there are lots of non-computable problems: Does machine T halt on input tape TT? Does machine T ever print a particular symbol? Does T ever stop when started on a blank tape? and so on. All of these allow the construction of a paradox and hence they are non-computable. Once you have a specimen non-computable problem you can prove other problems non-computable by showing that the new problem is the same as the old one. More precisely, if a solution to problem A can be used to solve problem B, we say that A can be reduced to B. So if we can show that a solution to A can be used to solve the halting problem, i.e. A can be reduced to the halting problem, then A is also undecidable. This is a standard technique in complexity theory, reduction, because while it is often difficult to prove something, it is easy to show that something is equivalent to what you have already proved. For example, the Busy Beaver problem is simple enough to state. Find the maximum number of steps a Turing machine with n states can make before halting i.e. find the function BB(n) which gives the maximum number of steps the machine takes. If this function exists you can use it to put a bound on the number of steps any machine could take and so create the function halt(T,t). If you have BB(n) you know that any machine that halt(T,t) has to process has to either halt in fewer than n steps or loop forever. We have reduced BB(n) to halt(T,t) therefore BB(n) is undecidable. Arguing the other way, there are some well known math problems that have solutions if the halting problem does. For example, Goldbach’s conjecture is that every number greater than 2 can be written as the sum of two primes. If the halting problem was decidable you could use halt(T,t) to solve the Goldbach conjecture. Simply create a Turing machine G that checks each integer to see if it is representable as the sum of two primes and halts if it finds a counter example. Now we compute halt(G,t) and if it returns true then G halts and the Goldbach conjecture is false. If it returns false then no counter example exists and the Goldbach conjecture is true. The fact that halt is non-computable rules out this approach to proving many mathematical conjectures that involve searching an infinite number of examples to find a counter example. The Problem With UnboundedIt is very important to note that hidden within all these descriptions is the use of the fact that a Turing machine has a finite but unbounded tape. We never ask if it is impossible to construct the paradoxical machine because of a resource constraint. In the real world the memory is finite and all Turing machines are bounded. That is, there is a maximum length of tape. The key point is that any Turing machine with a tape of length n, a symbol set of size s and x states (in the finite state machine) can be simulated by a finite state machine with a = s^{n}x states. We will return to this in the next chapter, but you should be able to see that a resource-limited Turing machine has a finite set of states – a combination of the states of the finite state machine and the states the tape can be in. Hence it is itself just a finite state machine. Why does this matter? Because for any finite state machine the halting problem is computable. The reason is that if you wait enough time for the finite state machine with a states to complete a+1 steps it has either already halted or entered one of the a states more than once and hence it will loop forever and never halt. This is often called the pigeon hole principle. If you have a things and you pick a+1 of them you must have picked one of them twice. There is even a simple algorithm for detecting the repetition of a state that doesn't involve recording all of the states visited. It is the unbounded tape that makes the Turing machine more powerful than a finite state machine because a Turing machine can have as many states as it likes. The fact that the Turing machine has an unbounded tape is vital to the construction of the halting paradox. You might now ask where the unbounded nature of the Turing machine comes into the construction of the paradoxical machine? After all we never actually say “assuming the tape is unlimited” in the construction. The answer is that we keep on creating ever bigger machine descriptions from each initial machine description without really noticing. An informal description is not difficult and it is possible to convert it into a formal proof. Suppose we have a bound b on the size of the tape we can construct – that is the tape cannot be bigger than b locations. Immediately we have the result that the halting problem can be solved for these machines as they have a finite number of states and hence are just finite state machines. Let’s ignore this easy conclusion for the moment and instead construct a machine that implements halt(T,t) then the function halt(paradox,paradox), which has to evaluate paradox(paradox), which in turn has to evaluate halt(paradox,paradox), which in turn has to … You can see that what we have is an infinite regression each time trying to evaluate halt(paradox,paradox). This is fine if the tape, or more generally the resources available, are unbounded and the evaluations can go on forever. Notice that the use of halt in paradox is an example of recursion – a subject we will return to in Chapter 16. What happens if the Turing machine is bounded to b tape locations? Then at some point it will run out of tape and the evaluation of halt(paradox,paradox) will fail and the whole set of evaluations will complete without ever having evaluated halt(paradox,paradox). That is, an error stops the computation without a result. In this case no paradox exists and we haven’t proved that halt(p,t) cannot exist, only that if it does exist there is a limit to the size of machine it can process. The halting problem can only be solved by a machine that uses a tape bigger than the class of machines it solves the problem for and this implies it cannot solve the problem for itself or any machine constructed by adding to its tape. You need a bit of infinity to make the halting problem emerge. Even if you expand the conditions so that the computing machine can have memory bounded by some function of the size of the input, the halting problem is still decidable. As soon as you have an unbounded set then there are questions you can ask that have no answer. If you still find this strange consider the following question. We have an arbitrary, but bounded by b, set of things – is it possible to compute a value n that is larger than the number of things in the set? Easy, set n≥b and you have the required number. Now change the conditions so that the set is finite but unbounded. Can you find a value of n? The answer is no. As the set is unbounded, the question is undecidable. Any value of n that you try can be exceeded by increasing the size of the set. In this sense the size of an unbounded set is non-computable by definition as it has no upper bound. The situation with the halting paradox is very similar. Another way of thinking of this is that the machine that solves the halting problem has to be capable of having a tape that is larger than any machine it solves the problem for and yet the machine corresponding to the paradox machine has an even larger tape. Just like n in the unbounded set, a Turing machine with the largest tape doesn’t exist as you can always make a bigger one. For the record:
Having said this, it is important to realize that for a real machine the number of states could be so large that the computation is impractical. But this is not the same as the absolute ban imposed by the undecidability of the halting problem for Turing machines. There are many other undecidable propositions and they all share the same sort of structure and depend on the fact that an unbounded tape means there is no largest size Turing machine and no restriction on what a Turing machine can process as long as it can just ask for more tape. Notice that humans are also finite state machines, we do not have unlimited memory, and hence there is no real difference, from the point of view of computer science, between a robot and a human. In book but not in this extract
Summary
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.Contents
<ASIN:1871962439> <ASIN:1871962587> To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@i-programmer.info |
||||||
Last Updated ( Monday, 16 December 2019 ) |