An In-Depth Look at Turing Machines

This essay has been superceded by Turing Machines: A Closer Look, but we have kept this here for completeness.

This essay is a more in-depth look into Turing Machines (TM) and their workings than we have previously seen. This essay will assume you have read the Turing Machines essay, or have some knowledge of the basic composition and working of a TM.

Naming Conventions

Before we start looking at anything let me firstly explain how I will represent the rules of a Turing Machine in this essay. Since this essay was primarily inspired by Penrose's The Emperor's New Mind I will use a similiar convention to Penrose. An example of some rules would look like:

00 to 01R.
01 to 11R.
10 to 00R. [stop]
11 to 11R.

The small letters are the states, the left-hand one referring to the state the machine is in, and the right-hand one referring to the state to change to. The large number on the left-hand side represents the data just read, and on the right-hand side the data to write. The 'R' means to move the tape right, 'L' means to move the tape left (not shown above) and [stop] means to stop the Turing machine (note I will abbrievate this further to merely S). Therefore, the instruction "01 to 11L" means "If in State 0 and a 1 is read, change to state one, output a one on the tape, and shift the tape left." The above 4 rules are the rules that govern unary addition - which is what Generation5's JavaScript Turing Machine demonstrates.

Movement

One thing that should be clarified too, is how I view the movement of the tape and the TM. While Penrose prefers to think of the TM to move, not the tape, I stick by Turing and say the tape moves. I also like to think of initial input to move in from the left, which the final output on the right of the machine. The diagrams below show this for unary addition:

Now that notation and movement has been cleared up, we will move on to the move complicated concept of the Universal Turing Machine.

The Universal Turing Machine

The concept of the Universal Turing Machine is a relatively simple one to grasp, with some incredibly complex implications. What you do is take an arbitrary TM (called T) and code the instructions required into a suitable form. These instructions are then read by the Universal Turing Machine (called U). The UTM can therefore simulate any turing machine! Now, all that is needed is a scheme to code a TM on to the 'paper tape' for our UTM to read and subsequently simulate.

Coding Turing Machines

There is no set way to code a Turing Machine (everything here is on a theoretical level), but a simple way to do it is by converting everything into a simple code, as follows:

0 = 0 = 00
1 = 1 = 10
L = 2 = 110
R = 3 = 1110
S = 4 = 11110

Therefore, we can code one of the above rules like this:

00 to 01R.
000000101110

Penrose uses some additional tricks and compression techniques to quite substantially reduce down the length of the instruction coding. For our purposes, though, I will not bother looking into such techniques. For simple Turing Machines (like the unary addition one), the final coded string is fairly manageable:

00000010111000101010111010000000111011110101010101110

Using this coding as a binary representation of a number, we can say that our unary addition turing machine is the 101,523,633,597,102nd Turing Machine using our representation! That's quite a large number considering the relative simplicity of the TM itself. I should note though that using Penrose's more complex coding scheme the TM is merely the 177,642nd machine - which is quite a saving.

What do these numbers mean, though? Aside from allowing a UTM to model them, they mean very little. They do not indicate complexity, nor do they indicate that they even work as Turing Machines! For example, let us take the 132nd Turing Machine. The binary representation of such a string is 10000100, which as our current scheme code stands in impossible to decode! In fact, let us look at what can be encoded:

000001101110 = 110
000011101110 = 238
000101101110 = 366
001011101110 = 750

You can see that in the first 750 Turing Machines, only 4 are valid! Now, this is a sign of my terrible coding scheme more than anything else. Nevertheless, on a natural number line, only a fraction of these TMs are valid Turing Machines. The interesting thing is that the Universal Turing Machine also has a number assigned to it. If anyone is enterprising (mad?) enough to attempt to calculate the number for this essay, I'd be very grateful. Needless to say, Penrose and Deutsch figured out the UTM number for Penrose's coding - the decimal number took a page and the binary coding took three!

The Non-Algorithmic Nature of Turing Machines

Alan Turing developed Turing Machines as a way to prove that not everything could be achieved algorithmically.¹ He found that there was no universal algorithm to determine whether a Turing Machine would stop. By universal algorithm, I mean an algorithm that works for all Turing Machines, and on all numbers and instructions possible.

I find it rather ironic, that Turing's findings are one of Penrose's chief arguments against Artificial Intelligence. The man that founded Artificial Intelligence is also the man that has sparked a lot of debate about whether it can ever be achieved.

¹ This was done to disprove Hilbert's Entscheidungsproblem.

Submitted: 17/01/2000

Printed from: http://www.generation5.org/content/2000/idturing.asp