The Universal Turing Machine

The solution to the difficulty of having to prove that you can implement every or any Turing machine is to notice that if a Turing machine can compute anything that is computable than there should be a Turing machine that can compute what any other Turing machine can do. This is a strange idea but it is the theoretical counterpart of today's general purpose computer. 

What you have to do is design a Turing machine that will take a description of any other Turing machine as its initial paper tape and then perform the computation that it would perform if it was built as a real Turing machine and not just a paper tape description. Such a Turing machine is called a Universal Turing machine because it can do the work of any other Turing machine.

This is of course the situation with our modern programmable computers. We don't need a distinct computer for each task and computation. We simply change the program and the hardware stays the same. So it is with a Universal Turing machine. You change the "program" on the paper tape and the Universal Turing machine effectively becomes the Turing machine described on the tape. From our point of view this is not so shocking but when Turing worked it all out it was fairly surprising and it lead on to some fundamental discoveries about the nature of computation.

So a Universal Turing machine can compute anything that any other Turing machine can. In a sense it is all of the Turing machines the universe can have in one small package. It is computation in a box and, if the Church Turing thesis holds, it is all the computation that can be done in a box. 

The Universal Turing machine has a huge advantage when it comes to proving that something is Turing complete. All you have to do is use it to implement a Universal Turing machine. If it can be done then you have proved that it can compute anything that any Turing machine can and hence it is Turing complete. All you have to do is implement one machine and if you can't do it then whatever it is can't possibly be Turing complete. 

Turing Complete Languages

Now we have a method that we can use to prove that a language is Turing complete. All we have to do is use the language to program a universal Turing machine. You can guess that it is fairly easy to show that anything with the three forms of flow of control, default, conditional and loops is Turing complete if it has something that works as a memory to simulate the paper tape. It is more difficult to prove that a language is not Turing complete because, rather than just demonstrating that you can program a Universal Turing machine, you have to prove that it is impossible to do so and proving that something is impossible is always much harder. Proving that something is impossible always carries with it the chance that you have just missed something and it is possible in some very complex and convoluted way. The usual way of proving that something is impossible is to try to find a contradiction if you assume that it is possible. 

The fact that you can write any program using just conditionals and loops is something of a surprise if you think that programming languages evolve into something increasingly complicated and sophisticated because the truth is that the simplest things you can think of are enough. 

This may be true but it isn't the whole truth. Turing machines and Turing Completeness are theoretical ideas used to test the fundamental strength of a language, but this doesn't make things practical. In the real world we have to value efficiency and Turing machines and simple Turing Complete languages are usually very slow and very inexpressive. In practice you don't want a computer language to have to use thousands of instructions to get something fairly simple done. It is a bit like the issue with the instruction: 

"Place 5 cherries on the top of the cake"

What type of instruction is it? A loop to repeat something simple five times or a single more complex instruction to do something more sophisticated just once? A practical programming language is exactly like this. Over time languages have evolved more complex instructions to make expressing tasks easier but these more complex instructions decompose back to the original simpler instructions. 

Nearly Everything Is Turing Complete

One of the most surprising things about the idea of Turing Completeness is that just about everything is. It seems that the bar to being able to compute anything that can be computed is very low. When people first started to investigate what was needed to create a language or a device that could compute anything, it seemed like an advanced property. After all computers back then were things which filled a small building and used a lot of power. It seemed obvious that computers were a rare and special thing and there is a sense in which this is stil true. An efficient compact general purpose computer is a difficult thing to build and you don't just find them in nature. 

What you do find in nature however is the potential to compute. Since the idea of Turing Completeness was invented an increasing number of unlikely devices and languages have been proved to be Turing Complete. Sometimes these things are called "accidental Turing Complete", but this hides the fact that being Turing Complete isn't a difficult thing to achieve. For example, many computer games including Dwarf Fortress, Minecraft and Conway's Game of Life are Turing Complete. Even card games can be Turing Complete - Magic: The Gathering is complex enough to be used to perform any computation that can be performed.  Even more unlikely are the number of physical systems which can be proved to be Turing Complete - water droplets, sliding block games and even the growth of slime mold can be used to compute anything. 

This idea pushed to its limit results in the idea of physical computation. The idea is that every physical system of even slight complexity is Turing Complete and its behaviour is a computation. Some physicists, but not many, believe that a theory of everything would be a theory of computation. The suggestion is not that we live inside a computer simulation created by some advanced aliens, but that the universe is a computer - most likely some sort of cellular automaton. 

Finally, as it seems that most things are Turing complete it makes it all the more interesting when we find something that seems to have expressive power but isn't Turing Complete. It is all the more interesting that the two little language introduced in Chapter 1 are not Turing Complete because neither has any way of writing a conditional. If we include a conditional into the geometric language then it becomes Turing Complete and, with a few more additions, the full computer language Logo. 

The language of arithmetic expressions may look complex:

((6+3)/(4-6)^6)*(28/33 +89)

but it has neither loops nor conditionals. It cannot be used to express an arbitrary algorithm. This is the main distinction between math and programming. When mathematicians need to express an algorithm they have often to move into a language-based description of what is to happen or write in a programming language. In many cases they hide the fact that an algorithm is involved at all by writing equations and simply commanding "solve for x" or similar. 

Summary

What have we discovered?

• That anything that can be practically computed can most likely be computed by a Turing machine - this is the Church Turing Thesis. 
• Any language or device that can compute what any Turing machine can is called Turing Complete.
• There is a particular Turing machine that can read a paper tape describing any other Turing machine and perform its computation. This is the Universal Turing machine. 
• To prove that a language or device is Turing Complete all you have to do is show that it can be used to implement a Universal Turing machine.
• A language that has a default flow of control, conditional execution and repetition is Turing Complete with only minor additional requirements.
• A surprising range of languages, games and devices turn out to be Turing Complete and this has led some scientists to suppose that the universe is in fact a computational device. Whatever the truth, viewing physical systems as computations is a novel and rewarding things to do. 
• Not everything is Turing Complete and things that seem complex and expressive that fail to be Turing Complete are of great interest.  

Comments

Make a Comment or View Existing Comments Using Disqus

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