Question

Find the output for the following Turing machine when run on the tape b1001b, assuming that the machine begins in state 1 and on the left side of the tape.

(1, 1, 1, 2, R)

(1, 0, 0, 2, R)

(1, b, 1, 2, R)

(2, 0, 0, 2, R)

(2, 1, 0, 1, R)

Answer 1

The initial configuration of the tape is given as b1001b.

The output of the turing machine is traced as follows :

Step 1 :

The first symbol scanned is the blank symbol b and the initial state given is state 1.

Using the transition (1, b, 1, 2, R), state 1 on seeing b goes to state 2,  replaces the blank symbol b by symbol 1 and the head moves towards the right.

The updated configuration is :

11001b

Step 2 :

The next symbol to be scanned is 1.

Using the transition (2, 1, 0, 1, R), state 2 on seeing 1 goes to state 1, changes the symbol 1 to symbol 0 and moves the head towards the right.

The updated configuration is :

10001b

Step 3 :

The next symbol to be scanned is 0.

Using the transition (1, 0, 0, 2, R), state 1 on seeing 0 goes to state 2, keeps the symbol 0 as it is and moves the head towards the right.

The updated configuration is :

10001b

Step 4 :

The next symbol to be scanned is 0.

Using the transition (2, 0, 0, 2, R), state 2 on seeing 0 remains in same state, keeps the symbol 0 as it is and moves the head towards the right.

The updated configuration is :

10001b

Step 5 :

The next symbol to be scanned is 1.

Using the transition (2, 1, 0, 1, R), state 2 on seeing 1 goes to state 1, changes the symbol 1 to 0 and moves the head towards the right.

The updated configuration is :

10000b

Step 6 :

The next symbol to be scanned is b.

Using the transition (1, b, 1, 2, R), state 1 on seeing b goes to state 2, changes the symbol from b to 1 and moves the head towards the right.

The updated configuration is :

100001

Hence, the required output of the given turing machine is :

100001