A Turing machine, as described by Turing, is an automaton that has:
a tape consisting of a sequence of cells of infinite length
a set of possible states, one of which is the current state
a transition function
a set of halting states
a read/write head that allows input and storage to be combined in a single tape of cells. This can move in both directions.
Turing compared the tape of cells to an exercise book with squares on the pages where the tape wraps to a new line: just as well that exercise books are not tapes of infinite length! Turing also compared the process of his machine with the way a human 'computer' would perform a calculation, focusing on one value, the current state of the brain and how to process that value.
Transitions are based on the current state and the symbol under the read-write head. Each transition involves three things:
Transition from one state to the next
Writing a symbol to the current cell
Direction to move the read/write head
One state is designated the starting state.
1. Create the Turing machine that creates the sequence 01010101... (Turing's first problem)
2. Implement these logical operators in Turing Kara:
| NOT | OR | AND |
3. Check that a binary string is made up of n zeroes followed by n ones (in B&L page 37). Implement the state transition diagram in Kara.
4. Add 1 to a number in unary:
B&L text book example on page 40, 1.4.7: Adding 1 to a unary number: 1, 11, 111, 1111... Implement this in Turing Kara.
state 1: read a 1, write a 1, go right
state 2: read a 1, write a 1, go right
state 2: read a space, write a 1, go right
state 3: read a space, write a space, go left
state 4: read a 1, write a 1, go left,
state 4: read a 1, write a 1, go left
state 4: read a 1, write a 1, go left
state 4: read a space, write a space, go right, stop
5. Take 1 away from a unary number. Implement this in Turing Kara.
6. Adding two unary numbers separated by a space or other character e.g. 11 111. (Page 42 in B&L)
7. Add two binary numbers e.g. 01 + 10. Binary addition
8. Create the Turing machine in Kara that produces the sequence 01011011101111011111. What does this represent (at least two answers).
These exercises show how far simple processes are broken down in order to carry them out on a machine.
On-Line Simulators
Study the examples in these on-line simulators.
| Alan Hodges | Ye Olde Turing Machine | A Turing Machine |
| Another Turing Machine |
If a Turing machine can be made to implement a certain computation then that Turing machine represents an algorithm for that problem. If a Turing machine exists then the solution to the problem is computable. Or, a task is computable only if it can be computed by a Turing machine. The Turing machine provides a rigorous definition of the algorithm. The algorithm is coded in the transition rules of the Turing machine. The Church-Turing thesis states that, if an algorithm exists, there is an equivalent Turing machine for that algorithm.
Computability was the original problem that Turing set out to investigate and the Turing machine was the conceptual tool that he used to analyse the algorithms.
A Turing machine's basic operations cannot be made any smaller: they are atomic. As a result, all other types of computing machine can be reduced to an equivalent Turing machine. So a Turing machine can do anything that a computer can do! A Turing machine also provides a formal definition of a digital computer. The rough equivalent of Turing machine instructions is machine code instructions. Different processors have different instruction sets but the underlying algorithm, as implemented on a Turing machine, is the same.
Turing showed that there was no solution to the Entscheidungsproblem of David Hilbert by showing that it was not possible to decide algorithmically whether a given Turing machine will ever halt. Hilbert's tenth problem was to find a process that could decide whether a given polynomial has an integer solution. Hilbert assumed that the algorithm for this problem existed: Turing showed that it did not, that the proposition was undecidable: there is no algorithm that can determine whether a polynomial has roots that are integers.
Turing showed that the halting problem is undecidable or cannot be solved by a machine like a computer. The halting problem is this: can we write a Turing machine (or program) that will take as input another program and decide whether that program will halt for any given input. Turing concluded that no such program could exist. For example, if the problem is this:
input x e.g. 5
while x <> 1 do
if x is even divide by 2
if x is odd set x to 3x + 1
then it is impossible to build a Turing machine that will decide, for any given input value, whether the sequence generated will reach 1 or whether it will continue for ever. Thus there are some problems that a Turing machine cannot solve; they are undecidable.
Implement a two-state busy beaver in Kara. Note the text book page 45 contains a mistake: transition from S1 to S2 is:
square|1 right
or
1 | 1 left
and transition from S2 to S1 is:
1 | 1 left
and
square | 1 left
Busy Beaver - find the Examples and implement the 1-, 2- and 3-state models.
A Universal Turing Machine (UTM) is a Turing machine that can execute other Turing machines by simulating the behaviour of any Turing machine. A UTM behaves as an interpreter, like a browser interpreting and executing a Java applet. The instructions for the Turing machine that is being simulated are data so data and instructions are effectively the same thing. This is the basic principle of the Von Neumann processor design (the Harvard architecture had separate buses for instructions and data; Von Neumann brought them together into a single bus; memory thus contained a mixture of instructions and data.
Computation is powered by UTMs. A computer can run existing programs and it can also run ones not yet invented because they will use the same model of computation. This contrasts with the world of devices such as radios, microwave ovens, cameras, TVs, etc. Each of these devices does one thing; if you want it to do something else you have to buy a different device. Mobile phones, being miniature computers powered by a processor and possessing an operating system that can control hardware and run programs, can accomplish a similar range of tasks to a computer: run a word processor, display web pages, run applets, take photographs, send texts and emails and even make phone calls (often the last thing that so-called mobile phones are now used for!)
In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation. A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left." and "If you are in state 2 and you see an 'A', change it to a 'C' and move right." in its rule set. (Wikipedia)
An ordinary (deterministic) Turing machine (DTM) has a
transition function that, for a given state and symbol under the tape head,
specifies three things: the symbol to be written to the tape, the direction
(left or right) in which the head should move, and the subsequent state of the
finite control. For example, an X on the tape in state 3 might make the DTM
write a Y on the tape, move the head one position to the right, and switch to
state 5.
A non-deterministic Turing machine (NTM) differs in that the state and tape
symbol no longer uniquely specify these things; rather, many different actions
may apply for the same combination of state and symbol. For example, an X on the
tape in state 3 might now allow the NTM to write a Y, move right, and switch to
state 5 or to write an X, move left, and stay in state 3.
How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks the transition which eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If any branch of the tree halts with an "accept" condition, we say that the NTM accepts the input.
These distinctions are used when considering intractable problems.
Not an A Level issue but completes Turing's work (Turing machine, war-time cryptanalysis, artificial intelligence). This adds a human dimension to a discipline that seems to be mainly about machines.
Video (between 11.30 & 20 minutes; there is a hard-to-hear introduction about a man risking his life for a primate)