MCQ on Turing Machines

A) The Turing machine M has:

States q and p; q is the start state.

Tape symbols 0, 1, and B; 0 and 1 are input symbols, and B is the blank.

The following next-move function:

State	Tape Symbol	Move
q	0	(q,0,R)
q	1	(p,0,R)
q	B	(q,B,R)
p	0	(q,0,L)
p	1	none (halt)
p	B	(q,0,L)

Your problem is to describe the property of an input string that makes M halt. Identify a string that makes M halt from the list below.

(a) 0110 (b) 0101 (c) 100101 (d) 10101

-

B) A Turing machine M with start state q₀ and accepting state q_f has the following transition function:

(q,a)	0	1	B
q0	(q0,1,R)	(q1,1,R)	(qf,B,R)
q1	(q2,0,L)	(q2,1,L)	(q2,B,L)
q2	-	(q0,0,R)	-
qf	-	-	-

Deduce what M does on any input of 0's and 1's. Hint: consider what happens when M is started in state q₀ at the left end of a sequence of any number of 0's (including zero of them) and a 1. Demonstrate your understanding by identifying the true transition of M from the list below.

a) q₀1100 |-* 1111Bq_f

b) q₀0101 |-* 1010Bq_f

c) q₀1100 |-* 1101Bq_f

d) q₀1010 |-* 0101q_f