4.4.5 -ToC (A model of computation) Flashcards
(6 cards)
1
Q
What is the universal turing machine
A
A turing machine that:
- Can replicate the behaviour of any other type of turing machine, by reading and interpreting its instructions allowing it to faithfully execute operations on data precisely the Turing Machine would, and that can compute any computable sequence
2
Q
What is stored first on the tape of a UTM
A
the instuctions and description of the arbitary Turing Machine it will replicate
3
Q
How does the UTM deal with the data and instructions from the TM
A
- It acts as an interpreter so, Interprets the TM’s instructions step-by-step, and executes it faithfuully as the TM would
4
Q
What is a turing machine
A
- A computer with a single fixed program, which provides a general model of computation and a definition of what is computable
5
Q
What are the 4 features of a Turing Machine
A
- 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
6
Q
When tracing turing machine in what order do you update the tape
A
State
Data
Head
