Exam-style question
Try this first
Use blank to denote a blank tape square. A Turing machine has start state q0 and halting state qh. Its transition rules are δ(q0, 1) = (q1, 0, R), δ(q1, blank) = (qh, 1, L), and δ(q1, 1) = (q1, 1, R). Represent these rules as state-transition-diagram edges and hand-trace the machine when the initial tape is 1 followed by blank squares. State the final tape contents in the first two squares and the final head position.
Model answer
What a good answer should say
- The state-transition-diagram edges can be written as q0 to q1, labelled 1/0,R; q1 to qh, labelled blank/1,L; and q1 to q1, labelled 1/1,R.
- The notation symbol-written,direction is used on each edge.
- Initially the machine is in q0, reads 1, writes 0 and moves right, entering q1.
- It then reads blank, writes 1, moves left and enters qh.
Explanation
Why this works
Each transition-function rule corresponds directly to one directed edge. The first part of the rule identifies the symbol being read; the remaining values identify the symbol written and the head movement.
The trace must update the state, tape and head position after each transition.
Common mistake
No common mistake is linked to this question yet.