Turing Machines and the Limits of Computation

1 Describe the components of a Turing machine. 4

One mark for each of the following, to a maximum of 4.

• A tape divided into cells, each holding a symbol, which is unlimited in length
• A read/write head that reads the symbol in one cell, writes a symbol, and moves left or right
• A state (from a finite set), including a start state and a halt (accepting) state
• A table of rules (transition function) that gives the symbol to write, the move and the next state for each state and symbol

Model answer. A Turing machine has a tape that is divided into cells, each of which holds one symbol, and which is unlimited in length. It has a read/write head, which reads the symbol in the current cell, can write a new symbol and then moves one cell left or right. It has a current state, from a finite set of states, which includes a start state and one or more halting states. It has a table of rules, the transition function, which says for each combination of state and symbol read what symbol to write, which way to move and which state to go to next.

2 The transition table shows a Turing machine. The tape holds the symbols 1 0 1 1 followed by blanks, the head is over the first 1 and the machine is in the state S0. State the contents of the tape when the machine halts, and describe what the machine does. 4

One mark for each of the following, to a maximum of 4.

• Reads 1, writes 0 and moves right, staying in S0 (and similarly for each symbol)
• Each 0 becomes a 1 and each 1 becomes a 0 as the head moves right
• When the head reaches a blank the machine halts
• The tape then holds 0 1 0 0

Model answer. The machine reads each symbol in turn, writes the opposite bit, moves right and stays in S0. So 1 becomes 0, 0 becomes 1, 1 becomes 0 and 1 becomes 0. When it reaches the blank at the end of the data it halts. The tape then holds 0 1 0 0. The machine inverts every bit of a binary number.

3 Explain what is meant by the halting problem, and why it is important. 4

One mark for each of the following, to a maximum of 4.

• It is the problem of deciding whether a given program, with a given input, will eventually stop or run forever
• Turing proved that it is impossible to write one algorithm that answers correctly for every program and input
• So it is an example of a problem that is non-computable (undecidable)
• It shows there are limits to what computers can do, for example a program cannot be written that finds every infinite loop (or every virus)

Model answer. The halting problem is the problem of deciding, for any program and any input, whether the program will eventually stop or will run forever. Alan Turing proved, by contradiction, that it is impossible to write a single algorithm that gives the correct answer for every program and input, which makes it an example of an undecidable, or non-computable, problem. It is important because it shows that there are limits to what computers can do, whatever their speed or memory. For example, it is impossible to write a program that is able to find every infinite loop in every other program.

4 Explain the difference between a tractable problem and an intractable problem, giving an example of an intractable problem. 4

One mark for each of the following, to a maximum of 4.

• A tractable problem can be solved by an algorithm in polynomial time (a reasonable amount of time)
• An intractable problem has no known algorithm that solves it in polynomial time; the time grows exponentially or worse as the input grows
• So an intractable problem cannot be solved in a sensible time except for small inputs
• An example, such as the travelling salesperson problem (or timetabling, or cracking a password by brute force)

Model answer. A tractable problem is one that can be solved by an algorithm whose running time grows polynomially with the size of the input, so it can be solved in a reasonable amount of time even for large inputs. An intractable problem is one where there is no known algorithm that runs in polynomial time. The time needed grows exponentially or worse as the input grows, so it can only be solved in a sensible time for small inputs. An example of an intractable problem is the travelling salesperson problem, where the number of possible routes grows factorially with the number of towns.

5 A company is developing a journey planner for a city's tram network. Discuss how abstraction and automation would be used in the development of the planner. 6

One mark for each of the following, to a maximum of 6.

• Representational abstraction: the network is shown as a graph of stops and connections, leaving out detail such as the shape of the track and the buildings
• Details such as distance or time between stops are kept as weights because they are needed
• Problem abstraction (reduction): finding a journey becomes a shortest path problem, which is already solved
• An algorithm such as Dijkstra's (or A star) is chosen to solve the shortest path problem
• Automation: the model and algorithm are implemented in code and executed so that routes are found automatically, quickly and consistently
• A reasoned point about the limits: the abstraction might leave out something important (delays, walking time), so the model must be checked

Model answer. Abstraction would be used to turn the real tram network into a simple model. The network can be represented as a graph, with stops as vertices and the connections between them as edges, leaving out details that a passenger does not need such as the shape of the track or the buildings, but keeping the travel time between stops as the weight of each edge. Problem abstraction then reduces the question 'what is the quickest way from A to B?' to a shortest path problem, for which there is already an algorithm such as Dijkstra's. Automation is then the process of implementing the model and the algorithm in code and executing it, so that the best route can be found automatically, quickly and consistently for any journey. The company would need to check that the abstraction has not left out something that matters, such as delays or the time spent walking between stops, since an over simplified model will give poor journeys.