Computing - Turing Machines
What two parts does a Turing machine consist of?
- A tape that can be read and write
- A controller that determines what happens at each cell
How long is the tape in a Turing machine?
Infinitely long.
What are the three states of a cell on some tape in a Turing machine?
$1$, $0$ or blank.
In a Turing machine, what moves along the tape?
A read-write head.
What state must a Turing machine have?
A halting state.
In a Turing machine, what is a controller?
A finite state machine which tells the machine what to do next.
What are the three things a Turing machine can do in any one state?
- Read any symbol on the tape
- Erase or write a new symbol
- Move the head left or right by a single space
In a Turing machine, what are the three parameters of a finite state machine?
Input, output, head movement.
Describe the 3 steps of the state transition $0,0,L$ for a Turing machine?
- A zero is inputed
- A zero is outputed
- The head moves left
What symbol is used to represent a state transition function?
Why is $\delta$ used as the symbol for the state transition function?
Because it means “small change”.
What is the general pattern of a state transition function?
What is a transition function?
A way to represent the transition arc between two states on a state transition diagram.
What does $\delta(S7, 1) = (S3, 1, R)$ mean?
If on state $S7$ and a $1$ is inputted, transition to state $S3$, write a $1$ and move the read-write head to the right.
For the input of $0$, what is the state transition function?
For the input of $0$, what is the state transition function?2021-01-04
Why is a Turing Machine useful?
Because the mathematical definition of a Turing machine defines what is computable.
Why is a Universal Turing Machine used?
Because otherwise a Turing machine would be needed for each operation.
What is the main difference between a Universal Turing Machine and a normal Turing machine?
- Turing machines have one specific purpose
- Universal Turing machines can be configured for different problems
What two things does a Universal Turing Machine read?
- The definition of a Turing machine
- Some input data
What idea did the Universal Turing Machine lead to?
The stored program computer.
What is a stored program computer?
A computer where the program andi ts data were stored in memory.
What kind of architechture is a stored program computer?
The von Neumann architechture.
Why is it not possible to create a Turing machine that solves the Halting problem?
There is no algorithm that solves the Halting problem.
Why is a Turing machine technically more powerful than any actual computer?
Because it has an infinite amount of memory.
2022-05-18
What is a common use of Turing machines in exam questions?
Calculating parity.