Now we have the Church-Turing thesis and the prime model of computation the Turing machine, it is time to ask what computations are out of reach. If you have not encountered these ideas before then prepared to be shocked and puzzled. However paradoxical it may all sound, it is, perhaps at the expense of some mysticism, very easy to understand.

First we have to look at the second good idea Turing had – the universal Turing machine.

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>

The Universal Turing Machine

Suppose you have a Turing machine that computes something. It consists of a finite state machine, an initial state and an initialized tape. These three things completely define the Turing machine.

The key idea in creating a universal Turing machine (UTM) is to notice that the information that defines a specific Turing machine can be coded onto a tape. The description of the finite state machine can be written first as a table of symbols representing states and transitions to states, i.e. it is a lookup table for the next state given the current state and the input symbol. The initialization information can then be written on the tape and the remainder of the tape can be blank and used as the work area for the universal Turing machine.

Now all we have to do is to design a Turing machine that reads the beginning of the tape and uses this as a “lookup table” for the behavior of the finite state machine. It can then use another special part of the tape to record the machine’s current state. It can read the symbols from the original machine’s initial tape, read the machine definition part of the tape to look up what it should do next, and write the new state out to the working area.

What we have just invented is a Turing machine that can simulate any other Turing machine – i.e. a universal Turing machine. Just in case you hadn’t noticed, a universal Turing machine is just a programmable computer and the description on the tape of another Turing machine is a program.

In that the universal Turing machine simulates any specific Turing machine in software, it is perhaps the first example of a virtual machine. You might think that this is obvious, but such ideas were not commonplace when Turing thought it up and implemented it. Even today you should be slightly surprised that such as simple device – a Turing machine – is capable of simulating any other Turing machine you can think of. Of course, if it wasn’t then the Church-Turing Thesis would have been disproved.

If you read about the universal Turing machine in another book then you might encounter a more complete description including the structure of the finite state machine and the coding used to describe the Turing machine to be simulated. All of this fine detail had to be done once to make sure it could be done, but you can see that it is possible in general terms without have to deal with the details. Be grateful someone has checked them out, but don’t worry about it too much.

What Is Computable? The Halting Problem

At this point it all seems very reasonable – anything that can be computed can be computed by a specific Turing machine. Even more generally, anything that can be computed can be computed by a universal Turing machine, a very particular Turing machine, by virtue of it being able to simulate any other Turing machine. All you have to do is give the universal Turing machine a description of the specific Turing machine you are interested in on a tape and let it run. The universal Turing machine will then do whatever the specific Turing machine did, or would do if you actually built it.

This all seems innocent, but there is a hidden paradox waiting to come out of the machinery and attack – and again this was the reason Turing invented all of this! It is known as the “halting problem”. This is just the problem of deciding if a given Turing machine will eventually halt on a specific tape.

In principle it looks reasonably easy. You examine the structure of the finite state part of the machine and the symbols on its tape and work out if the result halts or loops infinitely. Given that we claim that anything that can be computed can be computed by a Turing machine, let’s suppose that there is just such a machine called “D”. D will read the description of any Turing machine, “T”, and its initial data from its tape and will decide if T ever stops. It is important to note that D is a single fixed machine that is supposed to work for all T. This rules out custom designing a machine that works for a particular type of T or a machine that simply guesses – it has to be correct all of the time.

There are various proofs that the halting problem isn’t computable, but the one that reveals what is going on most clearly is one credited to Christopher Strachey, a British computer scientist. To make the proof easier to follow, it is better to describe what the Turing machines do rather than give their detailed construction. You should be able to see that such Turing machines can be constructed.

Christopher Strachey

1916-1975 

Suppose we have a Turing machine, called halt, that solves the halting problem for a machine, described by tape T, working on tape t:

halt(T,t) 
  if T halts on t then state is true
  else state is false 

gives true if the machine described by tape T working on tape t halts and false otherwise, where true and false can be coded as any two states when the Turing machine stops.

Now consider the following use of the halt Turing machine to create another Turing machine:

paradox(P)
  if halt(P,P)==true  loop forever
  else stop

Nothing is wrong with this Turing machine, despite its name. It takes a description of a machine in the form of a tape P and runs halt(P,P) to discover if machine P halts on tape P i.e. halts on its own description as data. If the machine halts then paradox doesn’t and if it doesn’t the machine does. This is a little silly but there is nothing wrong with the construction.

Now consider:

halt(paradox,paradox)

Now our hypothetical halting machine has to work out if paradox halts on it own tape.

Suppose it does halt, then halt(paradox,paradox) is true, but in paradox the call to halt(P,P) is the same because P=paradox, so it has to be true as well and hence it loops for ever and doesn’t halt.

Now suppose it doesn’t halt. By the same reasoning halt(paradox,paradox) is false and the if in paradox isn’t taken and paradox stops. Thus, if paradox halts, it doesn’t and if paradox doesn’t halt, it does – so it is indeed well named and it is a paradox and cannot exist.

The only conclusion that can be drawn is that halt cannot exist and the halting problem is undecidable.

At this point you probably want to start to pick your way through this explanation to find the flaw. I have to admit that I have cut a few corners in the interests of simplicity, but you can trust me that any defects can be patched up without changing the overall paradox.

Notice that a key step in constructing this paradox is the use of halt within the program you are feeding to halt. This is self reference and like most self references, it results in a paradox. For example, the well known barber conundrum is a paradox:

The barber is the "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

It is impossible to build a Turing machine that can solve the halting problem – and given we believe that anything that can be computed can be computed by a Turing machine we now have the unpleasant conclusion that we have found a problem that has no solution – it is undecidable.

We have found something that is beyond the limits of computation.