A Turing machine is being used as a computational model to add one to a unary number. A unary number is represented by a sequence of 1 symbols. The tape ini...
Question 1 Report
A Turing machine is being used as a computational model to add one to a unary number. A unary number is represented by a sequence of 1 symbols. The tape initially contains 111□, where □ is a blank cell, and the read/write head begins on the leftmost 1 in state q0. The machine moves right across existing 1 symbols. When it reaches the blank cell, it writes a 1 and moves left into state q1. It then moves right once and halts. The symbol written in a transition is shown before the direction of movement.
Here qH is the halt state. The notation read / write, direction labels each transition. Answer the questions about the operation and limitations of this model.
(a) State what the symbol □ represents. [1]
(b) State what the instruction R means. [1]
(c) Complete the transition from q1 when it reads 1: write __, move __, then enter qH. [2]
(d) Give the tape contents and head position after exactly three transitions. [2]
(e) Give one limitation of using this particular Turing machine. [1]
(f) Calculate the total number of transitions made before the machine halts. [2]
(g) Describe the tape contents, head position and state when the machine halts. [2]
(h) Compare this Turing machine with the turnstile FSM by giving one difference. [2]
Answer Details
(a) □ represents a blank tape cell [1].
(b) R means move the read/write head one cell to the right [1].
(c) In q1 when reading 1, write 1, move R, then enter qH [2].
(d) The first three transitions move over the three original 1s. The tape remains 111□, the head is on the fourth blank cell, and the state is q0 [2].
(e) This machine can only add one to a unary value [1]. Unary is also inefficient for large values.
(f) There are three moves across the original 1s, one transition writing the new 1 and moving left, and one final right move to halt: 5 transitions [2].
(g) At halt, the tape is 1111, the head is on the fourth 1, and the state is qH [2].
(h) A Turing machine has an unbounded tape that it can read and write. The turnstile FSM has a fixed finite set of states and no writable tape memory [2].
Download The App On Google Playstore
Everything you need to excel in your exams
