Week 3 - Turing Machines: Computation Flashcards
What happens when a turing machine transitions?
It reads the item at the tape head on the tape. Depending on the symbol, it will decide what state to transition to, and it will also write a specified symbol on the tape where the tape head is. Then the tape head moves a certain number of spaces to the left or right.
How do you write down the detail of a transition as a configuration?
yields
e.g.
qCurrent a1 a2 a3 … aN yields b qNew a2 a3 … aN
Where b is the symbol written to the tape during transition.
What happens if the tape head tries to move left when it is on the left most end of the tape?
The head remains in the same place and the computation continues.
What happens if the tape head trys to move right when it is on the right most symbol of the input string in the tape?
It can move right since the tape has empty spaces to the right of the input string.
What do you write in a configuration to show that you are now reading empty memory from the tape (No longer on the input string)
☐
How do you write the empty symbol in Turing machines?
☐
What changes in a Turing machine while it computes?
Current state
Current tape content
Tape head location
How do you write down the starting configuration?
q a1 a2 a3 … aN
How do you write down a transition using computation terms?
T(q, a) = (q1, b, R or L)
Where q is the current state, q1 is the new state.
a is the input symbol on the tape head, b is what is written to the tape at the tape head.
R or L is Right or Left and T is the transistion function symbol.
What is the accepting configuration?
The configuration in which the state is qAccept.
What is the rejecting configuration?
The configuration in which the state is qReject.
What are the two halting configurations?
Accepting configuration
Rejecting configuration
How do you define a turing machine accepts an input in computational terms?
A Turing machine accepts an input w ∈ Σ* if there exists a sequence of configurations:
C1, C2, C3, …, Ck
such that
i) C1 is the start configuration of input w
ii) for each i, where 0 > i > k Ci yields Ci+1
iii) Ck is an accepting configuration
What is a language called if it is recognised by a Turing machine?
A Turing-recognisable language.
What is a Turing machine called if it halts on all inputs? e.g. it nevers loops infinitely, and only accepts or rejects all inputs.
A Decider.
