AQA A2 Computing 1.4 Turing Machines

Question 1

Turing Machine

Answer 1

An FSM that controls one or more tapes, where at least one tape is of unbounded length

Question 2

Equivalent Turning machine

Answer 2

All other types of computing machine are reducible to an equivalent Turning machine

Question 3

Power of a Turning Machine

Answer 3

No physical computing device can be more powerful than a Turing machine. If a Turning machine cannot solve a yes/no problem, nor can any physical computing device

Question 4

Universal Turning mchine

Answer 4

A UTM, U is an interpreter that reads the description of any arbitrary Turning machine M and faithfully executes operations on data D percisely as M does. For single-tape Turning machines, imagine that is written at the beginning of the tape, followed by D

Question 5

Interpreter

Answer 5

an interpreter works its way through a set of instructions identifying the next instruction then executing it

Question 6

Principle of universality

Answer 6

a universal machine is a machine capable of simulations any other machine