Alan Turing’s Universal Computing Machine

A Turing Machine is a not a real machine, it is a theoretical idea which plays an important role in the foundations of mathematics and computer science. Turing Machine’s are useful for studying algorithms, they provide a language for describing certain abstract concepts in a precise way.

What is a Turing Machine?

A Turing Machine is capable of writing down a sequence of 0's and 1's on an infinite strip of tape; and each Turing Machine comes with a table of instructions for writing down it’s prescribed sequence.

The machine has a scanner; it is “aware” so to speak of only a single square at a time; it is capable of scanning this square, and of moving the scanner one space left or right.

The machine is capable of existing in a number of states, and the table of instructions tells the machine what to do next based on what state it is in, and what symbol is being scanned.

The number of possible states of the machine depends on the problem which it is capable of solving. To keep track of what state the machine is in, it makes use of a private strip of tape, which is called the “state register”.

Post-Turing Machine’s

The usefulness of Turing Machines derives from the fact that they model the process of computation, by breaking this process down into it’s indivisible parts.

A Post-Turing Machine is an alternative model of computation which is equivalent, in a certain sense, to Turing Machine’s as defined in the previous section. A Post-Turing machine has it’s own primitive programming language, and a Post-Turing Machine has an instruction pointer which keeps track of which line of code should be executed next.

There are only 7 instructions that a Post-Turing Machine knows how to execute, and each instruction is numbered according to the following list:

1. Print 0
2. Print 1
3. Move left one square
4. Move right one square
5. If scanned square is 0 move to instruction i
6. If scanned square is 1 move to instruction j
7. Stop

As an example, the Post-Turing Machine which writes down the sequence 101010… forever would begin with a strip of tape where each square has a 0 in it, and it would have the following instruction set.

1. (2) Print 1
2. (4) Move Right
3. (1) Print 0
4. (4) Move Right
5. (510) If scanned square is 0, goto instruction 1

The reader can easily construct many other examples.

The Description Number

Each Turing Machine corresponds to a single number, which is called it’s description number. The Turing Machine from the previous example has the description number 2414510, you can read the description number from left to right as: do instruction 2 (print 1), do instruction 4 (move right), do instruction 1 (print 0), do instruction 4 (move right); 510 means do instruction 5, which is to check if the scanned square is a 0, and then jump to instruction number 1 if it is. In other words a 0 in the description number acts like a closing parenthesis for a jump instruction.

Universal Turing Machine

A Universal Turing Machine is similar in many respects to a computer which can execute stored programs. It’s a Turing Machine that mimics other Turing Machines.

A Universal Turing Machine takes as input the description number of another Turing Machine, and produces as output the same sequence of 0's and 1's as that machine, by executing the instructions in the description number one at a time.

A modern computer is a Universal Turing Machine, and a desirable feature of a programming language is that it should be Turing Complete; which means that every problem that can be solved by a Turing Machine can also be solved by writing a program in that language.

What kind of problems can Turing Machine’s solve?

A Turing Machine can solve any math problem that can be solved by a sufficiently obedient human being with an unlimited amount of time and writing supplies. In other words, a Turing Machine can solve any problem for which there is an effective procedure for solving that kind of problem. An effective procedure is an algorithm which is guaranteed to provide a correct solution to a problem of a certain type.

An example of an effective procedure is long division. For any two numbers, there is a Turing Machine which will do long division to calculate the result of the problem.

A more interesting question is what kind of things can’t a Turing Machine do. The amazing fact is that there are some classes of problems for which no algorithm exists to solve the problem in general. An example of this type of problem is to find an algorithm to decide if a polynomial with rational coefficients can be solved in rational integers.

Computable and Non-Computable Numbers

Every real number between 0 and 1 can be written in binary notation as a decimal point followed by a sequence of 0's and 1's. If a sequence of 0's and 1's can be written down by a Turing machine, that sequence is said to be computable. The well known diagonal argument, pictured below, shows that the set of all sequences of 0's and 1's cannot be written down in an enumerated list; since given such a list, it is possible to use the list to construct a sequence of 0's and 1's which the list does not contain.

However, since every Turing Machine corresponds to a single number, it’s description number, and since the set of all description numbers is clearly enumerable, there must exist sequences of 0's and 1's which cannot be computed by a machine. These are the so-called non-computable numbers.

The Halting Problem

The Halting Problem can be stated in the following way: find the description number of a Turing Machine that takes as input the description number of a Turing Machine, and which prints 0 if the machine corresponding that that description number will run forever (in a loop), and prints 1 otherwise.

A more modern way to pose the problem would be to ask for a computer program which is capable of reading any compiled binary file, and to determine if the program will stop running, possibly by crashing, or if it will run forever.

The Halting Problem has no solution, because there is no effective procedure for solving this class of problems in general. To see why this is true, consider the following approximate argument:

Assume that it was possible to solve the Halting Problem, and let T be the Turing Machine which given any description number will always terminate on either 0 or 1, depending on whether that description number corresponds to a Turing Machine that runs forever or not.

Let D be the description number of T. When T checks it’s own description number to determine if it runs forever or not, it will terminate because of our assumption that it always terminates.

But when it checks it’s own description number it will run forever, which is a contradiction, and therefore the assumption that it is possible to solve the Halting problem must be false.

To see why T will run forever when it checks it’s own description number, consider how this program must proceed. You give it an infinite list of all the description numbers for all possible Turing Machines, and it checks them one by one. When it gets to its own description number it has to start checking them all over again from the beginning; and so it get’s trapped in an infinite loop.

The Complexity of Algorithm’s

One of the reasons why Turing Machines are useful is for measuring the complexity of an algorithm. Given a Turing machine which executes an algorithm by carrying out a finite number of steps, the complexity of the algorithm is measured by counting the number of steps it takes before terminating.

The number of steps an algorithm requires before terminating depends in general on the size of the input, N. For example, sorting a list of size N, or finding the prime factors of N.

Suppose that we have some problem for which there is an known effective procedure. If there is a function f(N) which gives the number of steps the algorithm takes to complete, then it is customary to use Big-O notation to express the complexity of the algorithm.

For example, to sort a list of numbers of size N, we can use an algorithm which takes N-squared steps to complete: create a new list, then read the original list of numbers N times, and each time you read the list take the smallest number not already on the new list, and add that number to it. Since it takes N steps to read the list one time, the total number of steps is N*N, or in Big-O notation, O(N^2).

P vs NP

If it’s possible to find a formula f(N) for the number of steps a given algorithm takes to complete in the form of a polynomial in N, for example N^2 then we say the algorithm takes “polynomial time” to complete. If this formula is not a polynomial in N, for example 2^N, then the algorithm is said to take “non-polynomial time” to complete. The famous and unsolved P vs NP problem asks whether or not there are problems which can only be solved by algorithms that complete in non-polynomial time.

How Computers Work

Instead of a infinite strip of tape, a modern computer has an extremely large amount of memory which contains a sequence of 0's and 1's. A computer also has a system of registers it uses in the course of it’s operation, which correspond to the “state register” of a Turing Machine.

A stored program has a description number, which is it’s compiled binary file, and the CPU is capable of executing the instructions contained in this file.

The operating system defines a set of machine code instructions for interacting with the underlying hardware; as well as an Assembly Language which makes it possible to write programs using these instructions. The assembly language can be converted into a binary file very easily, and higher level languages compile to assembly first, and then to a binary.

A computer also has an instruction pointer which keeps track of which instruction should be executed next, and assembly language has commands such as if…else, and goto.

tl;dr

The credit for inventing the modern computer belongs to many people, but this invention was only possible because of the very profound idea’s of Alan Turing on the theory of computation. These idea’s provide an important tool for analyzing algorithm’s, and measuring their complexity; and they also have a number of important applications in pure mathematics as well.