Turing machines

Overview

Recall questions on the tape, start and halting states, the transition function and its diagram, and hand-tracing a machine over a given input.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a Turing machine?

   Model answer

   A Turing machine is a theoretical model of computation: a machine running one fixed program, expressed as a finite set of states drawn as a state transition diagram, together with a finite alphabet of the symbols it may read and write, an endless tape divided into squares, and a sensing read-write head that examines one square at a time and can travel along the tape. Each step reads the symbol beneath the head and, on the basis of the current state, writes a symbol, shifts the head one square left or right, and enters a new state.

2. 2

   List the four components a Turing machine's fixed program is expressed with.

   Model answer

   Its program is given by four things: the states, finite in number and normally drawn as a state transition diagram; the alphabet, also finite, of symbols that may appear on the tape; the tape itself, endless and marked off into squares; and a sensing read-write head that examines the square it rests on and moves one square at a time along the tape.

3. 3

   Describe the tape of a Turing machine as it is used in examination questions.

   Model answer

   One tape only, infinite in one direction. It is divided into squares, each holding a single symbol from the machine's alphabet, with blank squares represented by a special blank symbol that is part of the alphabet. The input is written on the tape at the start, the head begins at a specified square, and the tape serves as both the input, the working store and the output — whatever remains on it when the machine halts is the result.

4. 4

   What is the start state, and what is a halting state?

   Model answer

   The start state is the one the machine occupies before it has read anything, so computation begins there. A halting state is one from which no transition leads: on reaching it the machine has no rule left to apply and therefore stops. A machine that never arrives at such a state simply carries on forever.

5. 5

   What is the transition function of a Turing machine?

   Model answer

   The transition function is the machine's rules written as a mapping. It takes the current state together with the symbol currently under the head, and gives the next state, the symbol to write in that square and the direction to move the head, left or right. It is commonly written as δ(current state, symbol read) = (next state, symbol written, direction), for example δ(S0, 1) = (S1, 0, R).

6. 6

   How does a transition function relate to a state transition diagram?

   Model answer

   They are two ways of writing down the very same set of rules, and each converts mechanically into the other. A single line of the transition function, δ(Sa, x) = (Sb, y, D), becomes a single arrow in the diagram: it runs from Sa to Sb and carries the label x/y, D — read x, write y, then move in direction D. Nothing can be stated in one form that cannot be stated in the other. The tabular form makes it easy to confirm that every combination of state and input symbol has been given a rule; the diagram makes the loops and the machine's overall shape visible at a glance.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.