State the three components of a Turing Machine.
- A FSM.
- A read-write head.
- A tape which is infinitely long in one direction.
State the purpose of the read-write head of a Turing Machine.
Focusing on one cell at a time, the read-write head can read from, and overwrite the symbols on each cell, in sequential order. It may move or right along the infinite tape.
Describe the tape used within a Turing Machine.
- Infinitely long in one direction.
- Divided into cells.
- Each cell contains a symbol.
- The set of symbols used is called an alphabet.
- The alphabet must be finite.
Explain why Turing Machines are thought to be more "powerful" than FSM as a model of computation.
The tape is infinitely long in one direction, so it can utilise a greater range of languages than a FSM.
In plain English, describe this Transition Function: δ (S0, 1) = (S1, 1, R).
From current state S0, if the input is [], write 1 to the current cell, move to S1 state, Move Right along the tape
Write a transition function for S0 to S1 in this FSM.
δ (S0, 1) = (S1, 1, R)
Answer
Compare regular Turing Machines to the Universal Turing Machine.
Regular Turing Machines are limited to one FSM, and thus specific to one computational problem. While Universal Turing machines can represent any FSM.
Explain how Universal Turing Machines can represent any FSM.
A description of the FSM is stored on the same tape, the input data which is to be processed is. Therefore it is also an implementation of the stored-program concept.
State the moniker given to a Universal Turing Machine which reads instructions in sequence before executing operations on their input data.
Interpreter
Explain the importance of Turing Machines to computation.
It is a formal model of computation, which defines what can be computable. Meaning it can be used to ascertain which problems are solvable by computers.