At the forefront of Artificial Intelligence

Turing Machines: A Closer Look

We will be looking at Turing Machine from a much more theoretical point of view. This essay will assume you have basic knowledge of computational theory - i.e., (non-)deterministic finite automata, regular expressions, and simple set theory.

Turing Machines: The Definition

In general, while computer scientists like to look at TMs from the perspective of input and output, we will look at them from a more theoretical perspective - input is put in, and the TM outputs "yes" or "no" depending on whether it accepts the input or not. Incidentally, all computations can be reduced to this sort of scenario. With this in mind, Turing Machines can be represented using a 7-tuple:

Equation

A few things probably need clarifying here. Firstly, the difference between the input alphabet and the tape alphabet. The tape alphabet is a subset of the input alphabet, since the TM might require additional symbols to record states. Secondly, the transition function states that given a state in Q and a tape symbol, the TM transitions to another state in Q, a symbol is written on the tape (this can be the same symbol), and the tape moves left or right.

Visualizing Turing Machines

A Turing Machine can be represented as a deterministic finite automaton. For example, below is an NFA representation of a Turing Machine that accepts the regular expression 'aba*'. Note that for x/y, z x is the input symbol, y is the output symbol, and z is movement of the tape. Additionally, in the diagram, B implies a blank and S implies no movement of the tape.

Equation

For comparison, here is this Turing Machines set of transition states:

Equation

I'll leave it as an exercise to the reader to confirm that the TM indeed verifies any string in the regex 'aba*'.

Enumerating Turing Machines

There are many ways to encode a Turing Machine, only one of which will be covered here. Assume that the TM (T) the tape alphabet consists of {0, 1, B} where B is the Blank symbol. Rename all states in the TM as q₁...q_k, the tape alphabet as X₁...X_m, tape directions as D₁ (left) and D₂ (right).

Now, for each transition rule in the TM, we redefine it as:

Equation

We can now encode our TM rules as 0^m10ⁿ10^x10^y10^z. For example, using our aba* Turing Machine (where the tape alphabet is {a,b,B} instead of {0,1,B}), we could encode our first rule as follows:

Equation

Doing this for all our transitions we get the following rule encodings:

01000100100010
001010001010
0001001000010010
000010100001010
00001000100000100010

To simplify things, for the final transition rule, the Stop symbol has been replaced by a Left, for purposes of encoding since it doesn't affect the outcome of the Turing Machine. Finally, we can sort the encoded transition rules. Encoding is intuitively done; if the length of x is shorter than y, x is less than y. Failing that, x is less than y, is the first differing symbol in x is a 0. Now, sorting our rules gives us:

001010001010
01000100100010
000010100001010
0001001000010010
00001000100000100010

One way of enumerating TMs from this point, is to append all rule transitions together, and calculate the binary value. Doing this for our TM, makes it the 23,990,643,778,458,216,335,394^th in our encoding scheme!

...and why?

Probably the question on your mind at this point is quite why we want to be doing this. Encoding TMs like this allows them to be decoded and run using a Universal Turing Machine. This will hopefully be discussed in a later article.

Submitted: 10/04/2003

Article Toolbar

BibTeX entry