Reduction

As 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 Unbounded

It 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ⁿ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:

• All real physical computing devices have bounded memory and therefore are finite state machines, not Turing machines, and hence they are not subject to the undecidability of the halting problem. 

• A Turing machine has an unbounded tape and this is crucial in the proof of the undecidability of the halting problem, even if this isn’t made clear in the proof.

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

• Non-Computable Numbers

Summary

• The universal Turing machine can simulate any other Turing machine by reading a description of it on its tape plus its starting tape.

• The halting problem is the best known example of a non-computable or undecidable problem. All you need to do to solve it is create a Turing machine that implements halt(p,t) which is true if and only if the machine described by tape p halts on tape t.

• Notice that the halting program has to be solved for all Turing machines not just a subset.

• If halt(p,t) exists and is computable for all p and t then it is possible to use it to construct another machine paradox(p) which halts if p loops on p and loops if p halts on p. This results in a paradox when you give halt the problem of deciding if halt(paradox,paradox) halts or not.

• The halting problem is an archetypal undecidable problem and it can be used to prove that many other problems are undecidable by reducing them to the halting problem.

• If the halting problem were decidable we could answer many mathematical question such as the Goldbach conjecture by creating a Turing machine that searches for counter examples and then using halt to discover if a counter example existed.

• The undecidability of the halting problem for Turing machines has it origin in the unboundedness of the tape.

• A Turing machine with a bounded tape is a finite state machine f for which halt(f) is computable.

• The reason that the proof that halt is undecidable fails if the tape is bounded is that it involves a non-terminating recursion, which requires an infinite tape.

• All real computers, humans and robots are subject to finite memory and hence are finite state machines and are not subject to the undecidability of the halting problem.

• It is possible to create numbers that are not computable using undecidable problems such as halt(p,t) – such as the number with its nth bit is 0 if the nth Turing machine halts and 1 if if doesn’t. Such numbers are based on the unboundedness of the Turing machine.

• There is a class of non-computable numbers that in a sense are even more non-computable. There are only a countable number of Turing machines, but an uncountable number of real numbers. Therefore most real numbers do not have programs that compute them.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<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

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info