4.4.5.1 Turing machine

Question 1

Explain why the Turing Machine model can be used to recognise a greater range of languages than an FSA could.

Answer 1

Turing Machine has (an infinite / unlimited amount of) memory / storage;
Turing Machine can read and write / input and output (data) to / from a tape;
Turing Machine has infinitely long tape

Question 2

Explain the importance of the theory of Turing machines to the subject of computation

Answer 2

Turing machines provide a (general/formal) model of computation;
Provides a definition of what is computable // a task is computable if (and only if) it can be computed by a Turing machine;
No computing device can be more powerful than a Turing machine // any algorithm that can be computed by any computer can be computed by a Turing machine;

Question 3

Explain what a Universal Turing machine is

Answer 3

A Turing machine that can execute/simulate the behaviour of any other Turing machine
Faithfully executes operations on the data precisely as the simulated TM does
Description of/Instructions for TM (and the TM’s input) are stored on the (Universal Turing machine’s) tape

Question 4

What makes up a turing machine?

Answer 4

• a finite set of states in a state transition diagram
• a finite alphabet of symbols
• an infinite tape with marked-off squares
• a sensing read-write head that can travel along the tape, one square at a time

Question 5

What is the halting state?

Answer 5

The state with no outgoing transitions