Turing Machine Overview

Author: Peter Bradley

In the last module, we learned how to specify a set of rules for transforming symbols. But that is only half of the job. We also need to specify a set of symbols upon which those rules can operate. Let us start with a very simple example: Let us start a symbol with the character '0'. Then, the number of '1's following the 0 determines the number that symbol represents. So, the string '01' represent the number one. The string '011' represents the number two. The string '0111' represents the number three, and so on.

Now that we have a symbolic language to represent the natural numbers, we can begin creating machines that can operate on those numbers. Here is a simple machine that will calculate the sum of two numbers using our symbolic language:


Turing Machine for Addition

We say that a function is 'Turing-computable' if its value can be computed by a Turing machine. The 'sum' function takes two inputs and produces one output: the sum of the two inputs. The successor function produces the next number of any number. For reasons that I cannot explain here, the most interesting function for creating a system of arithmetic is the successor function — a function that produces the next number of any number. The following Turing machine shows that the successor function is Turing-computable:


Turing Machine for the Successor Function

This is simple simulation of a Turing machine designed to calculate the successor function (ƒ(a) = a 1). The machine table used here appears in Kleene, 1967.

So why are these little machines so incredibly interesting? First, in these cases, we have interpreted the symbolic language to stand for numbers, but we need not do so. The interpretation of the symbolic language used by the system is independent how the system operates on those symbols. The transformation rules (contained in the machine table) do not contain anything explicitly interpreting the string '01' as the number one. The machine operates on the symbols without reference to their interpretation — it operates in a purely syntactic way.


Copyright: 2002