Turing Complete

Default, loops and conditionals – is this all there is?

The answer seems to be yes. 

You might think that there would be a hierarchy of programming languages. Simple ones for simple things and increasingly more advanced languages that can do things that were impossible in the earlier languages. There would be some sort of smooth transition in ability and complexity as you move from one type of language to another. This isn't the way the world is organized and rather than a hierarchy we are faced with a simple categorization. In other words, there are only two major categorizations of language.

A programming language is either Turing Complete or it isn't. Languages that are not Turing complete are often referred to as little languages that we looked at earlier.

I guess the first question is what does Alan Turing, the UK mathematician known for his work as a World War II code breaker, have to do with this and what is a Turing Machine?

Turing was a pioneer in thinking about what computation is all about and, in particular, what you needed to perform a calculation. He set up a model of what most people would find acceptable as “computation”. Imagine a human in a room with a book and paper and pencil. The paper and pencils were considered to be unlimited, but the book contained a fixed number of simple instructions on what to write on the paper based on what was already written on the paper. The human in the model was considered to be an unintelligent robot who simply looked up instructions in the book based on the previous instruction and the contents of the paper.

This was similar to how difficult computations were performed at the time by human “computers”. People with limited knowledge of what they were doing simply followed a recipe for what they should do without any real understanding of the process and yet they performed complex mathematical calculations. Turing’s model was a simplified and reduced form of this approach to computation.

What we have described is a rough-and-ready formulation of a Turing Machine, something that can perform computations. Turing went on to make the definition even more precise by removing the human and the book from the picture and substituting a device, a finite-state machine, that did the same job. He also replaced the paper and pencil by a paper tape. This form of Turing Machine is more clearly mechanical and divorced from human intelligence, but it does the same job.

You might be thinking that a Turing Machine just does arithmetic, but in fact it is even more basic than this – it isn’t even up to the skills of a pocket calculator. All a Turing Machine can do is look at the symbol on the paper tape, look them up in the book and write a new symbol on the paper a result of the rule in the book.

To give you an example of a simple Turing Machine consider the rules:

1. If tape reads blank, write a 0, move right and do instruction 2

2. If tape reads blank, write a 1, move right and do instruction 1

The entire tape is assumed to be blank when it is started and so the Turing Machine writes 010101010101 … and so on forever.

This is a very simple Turing Machine, but things can become much more complicated. You can, for example create a Turing Machine that writes the digits of Pi on the tape or works out your total tax bill, assuming the tape starts off with the initial data.

Turing hypothesized that his machine could compute anything that was computable. Today this is called the Church-Turing thesis in honor of Alonzo Church whose work that was similar to that of Turing. 

Notice that you cannot prove that a mechanism like the Turing Machine can compute anything that is computable, but to date no one has found an example of something that it cannot compute but some other process can.

In one sense you can think of the Turing Machine as a definition of what it means for something to be computable. It is the very essence of computation.

Even though a Turing Machine is simple, and isn't the only way to define computation, it is the usual way of defining what is computable and what is able to compute it. So far, every alternative definition of computation has been shown to be equivalent to a Turing Machine.

It is very important to be clear about what we are defining. If a Turing Machine can compute something then it is Turing computable. The Church-Turing hypothesis has nothing to do with what is or is not computable, but it does mean that anything that is computable in any way is also Turing computable.

Also notice that the Turing Machine provides a test of how powerful a computing device or language is. If the device cannot compute something that a Turing Machine can then it isn't as powerful. For example. the little languages in Chapters 1 and 2 cannot compute things that a Turing Machine can but, of course, a Turing Machine can implement any little language.

As already stated if a computing device can compute anything a Turing Machine can then it is called Turing-complete, so our little languages are not Turing-complete. 

Proving Turing Completeness

Generally you don’t need to prove that something is Turing-complete because someone will usually have done the job for you! However, knowing a little about how to prove that something can compute anything tells you quite a lot about it.

To prove that something isn't Turing-complete all you need is an example of something a Turing Machine can compute and a proof that the device or language cannot compute it. Such a proof is often difficult, but at least all you have to do is search for a single example that cannot be computed by the system in question. For example, in the explanation of why the regular expression little language isn’t Turing-complete it was pointed out that it couldn’t detect a simple palindrome. Of course, any Turing-complete language can do the job and this isn’t difficult to demonstrate. To know that regular expressions cannot detect a palindrome gives you a clue as to what it lacks – in this case the ability to count and compare.

A more difficult task is to prove the opposite – that something is Turing-complete. To do this you have show that it can compute everything a Turing Machine can and this is an infinite task as there are infinite possible Turing Machines. Fortunately there is a shortcut to infinity in the form of simulation. If you can use the system in question to implement any Turing Machine then clearly it can compute anything that a Turing Machine can. Rather than worrying about replicating what an arbitrary Turing Machine can compute you can simply prove that the language can implement any Turing machine.

Thus a language or computing device is Turing-complete if it can be used to implement any Turing Machine.

This is an easier definition of Turing-complete, but notice that it isn't enough just to show that you can use the language to implement a single, or even a few, Turing Machines. You have to show that it is possible to implement any Turing Machine. In this sense it is still an infinite problem. It seems we really haven’t made any progress, but, with one addition, we have.