4.4.5 -ToC (A model of computation)

Question 1

What is the universal turing machine

Answer 1

• A turing machine
• That can execute the behaviour of any other Turing machine
• Can compute any computable sequence
• Faithfully executes operations on the data precicely as the TM machine does

Question 2

Where are the instuction of the arbitary Turing Machine stored on the UTM

Answer 2

• On its tape

Question 3

How does the UTM deal with the data and instructions from the TM

Answer 3

• It acts as an interpreter

Question 4

What is a turing machine

Answer 4

• A computer with a single fixed program, which provides a general model of computation and a definition of what is computable

Question 5

What are the 4 features of a Turing Machine

Answer 5

• 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