Basics of Computability - Describing A Turing Machine - C2

Now that we have gone over the purpose of a Turing Machine, it’s time to describe what it is.

Human Computers

To understand the historical context behind the way Turing machines are designed, we first note that historically:

A computer was once defined as a person who does calculations.

Now imagine you are asked to add two numbers together: 10+20. This is a computational task, lets use this example to discover what we may need in order to define a Turing Machine.

1. We need paper to write down the initial numbers we would like to add.

For simple numbers we could add them in our heads, however we are trying to generalise.

2. We need a pen to write the initial numbers with, and carry out the calculations for the task.

3. We need to define what characters are allowed. For example “!0 + 10” may not be a calculation that you are interested in because “!” is not a valid allowed character.

If you’ve just read the primer on computability chapter, the definitions stated there may now seem to have utility.

4. Note also that there is another set of characters that can be written on the paper, during calculations. For example, when doing calculations we are allowed to “cross out” a number when the digit carries. However, this “crossing out” character cannot be added as it is not a digit, so it does not belong in the first set of characters.

5. As a human, we need a way to read the numbers. If we were blind, we would not be able to see the calculation.

You could also use Braille if you were blind. Lets use the word “see” in it’s most liberal form. Observe might be a better word.

6. Once the numbers are written on the paper, we need an initial starting point. For addition using the schoolbook method, we usually start from the right most digit and add column wise while moving to the left.

7. Moreover, we need to know when the task has completed successfully or if it has completed but due to an error. For example; if the problem was to add “a2+10”. We would finish and reject this task because we are assuming that only digits can be added.

8. We need some sort of logic to tell us what to do at each given step.

In a round-about way, we have defined all of the components needed for a Turing Machine!

Turing Machine - Informal Definition

Before we check out the formal definition of a Turing Machine. Lets use the eight points above to informally define our Turing Machine by comparison.

1. A Turing machine has a tape which acts as memory for any task to be completed. Without loss of generality, we will assume the tape is 1 dimensional and is unbounded in both directions.

Here tape is synonymous with paper or memory. We say that it is unbounded but not unlimited, which accurately reflects our notion of memory; If you run out of memory, you can get more, but you do not have an unlimited source of memory.

2. A Turing machine has a head that writes symbols on the tape.

Here head is synonymous with pen or in some sense, the cursor.

3. A Turing machine has an input alphabet, which is the set of all characters that are allowed to be written to the tape initially. This excludes any “scratch characters” or “blanks”.

The input alphabet can be seen as the digits in the previous example. At the start of our computation, we do not have any scratch characters, because we have not started computing yet.

4. A Turing machine has an tape alphabet, which is the set of all characters that are allowed to be written to the tape. During the calculations, one may wish to cross out a character or insert blanks, hence these will be a part of the tape alphabet. Note that the input alphabet is contained in the tape alphabet.

You can think of the input alphabet as all of the symbols in the tape alphabet except the scratch characters and blank character.

5. The head is also capable of reading symbols from the tape. We will therefore call it a Read/Write Head.

In addition to being a pen, the head can also be seen as the eyes.

6. A Turing Machine has a initial starting state.

In other words, all algorithms must start somewhere. For addition of two numbers, if you use the column method, you always start from the right most digit.

7. A Turing Machine has finishing states. When a Turing machine gets into one of these states, we say that the Turing machine has halted. We may make the distinction between halt and accept/succeed and halt and reject. In both cases the Turing machine has stopped.

In the former case, the Turing machine has signalled an accept, the meaning of this depends on the context. If we were adding numbers together, the accept would signal that the numbers were successfully added and the answer is written on the tape. If the Turing machine was answering the question of “Is this number even?” the accept signal would indicate a “yes”. A similar logic can be followed for halt and reject.

8. A Turing machine has an instruction table / transition function that tells it how to move, what to write and what state to go to next, based on what it has already read and what state it is currently in. This can be seen as the control unit for the Turing Machine.

In the above example, this instruction table could be a large book which tells us where to move the pen, what to cross out, what to write down next, etc.