Exam-style question
Try this first
A Turing machine starts in q0 with its head on the first symbol of the tape. The tape initially contains 11 followed by blank squares. Its rules are: δ(q0, 1) = (q0, 1, R) and δ(q0, blank) = (qh, 1, L). What is on the first three tape squares when the machine halts?.
- A.110
- B.111
- C.011
- D.The tape is unchanged as 11 followed by a blank
Model answer
What a good answer should say
- 111
Explanation
Why this works
The machine moves right over both existing 1 symbols. When it reaches the blank third square, it writes 1, moves left and enters qh.
The first three squares therefore contain 111.
Common mistake
No common mistake is linked to this question yet.