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 then 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 led 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 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 the language to implement a Universal Turing Machine. If it can be done then you have proved that the language can compute anything that any Turing Machine can and hence it is Turing-complete.

This is much simpler. All you have to do is implement just one particular Turing machine and if you can't do it then whatever it is you are using 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 missed something and it really 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 given that programming languages tend to evolve into something increasingly complicated and sophisticated because it provides evidence 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 value efficiency, and Turing Machines and simple Turing-complete languages are usually very slow and very unexpressive. 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 describing tasks easier but these more complex instructions decompose back to the original simpler instructions.

Turing-complete languages may be theoretically all you need, but in the real world computer languages evolve into something more sophisticated and more efficient. Languages tend to bundle lots and lots of simple instructions into one big instruction and this is even a basic principle of programming, see Chapter 9 on modules.

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 still true. An efficient, compact, general-purpose computer is a difficult thing to build and you don't 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 are described as being "accidentally” 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 behavior 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. The two little languages introduced earlier are not Turing-complete because neither has any way of writing a conditional or a loop. If we include a conditional and a loop into the geometric language then it becomes Turing-complete, or perhaps whimsically Turtle Turing Complete, and, with a few more additions, it becomes the practical 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 mathematics and programming. When mathematicians need to express an algorithm they often have to provide a language-based description of what is to happen, the equivalent of writing a program. Sometimes they go the whole way and use a programming language – often made up for the purpose to express exactly what is to happen.

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. Mathematics does have ways of describing algorithms, but they are clumsy and incomplete compared with an equivalent description as a program.

Summary

• Anything that can be practically computed can most likely be computed by a Turing Machine – this is the Church-Turing thesis. 

• Any programming 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 programming 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 exercise. 

• Not everything is Turing-complete and things that seem complex and capable that fail to be Turing-complete are of great interest so that we can examine the reasons they fail.  

Comments

Make a Comment or View Existing Comments Using Disqus

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