MCQ: We wish to perform the reduction of acceptance by a Turing machine to MPCP.

Question

MCQ:

We wish to perform the reduction of acceptance by a Turing machine to MPCP. We assume the TM M satisfies Theorem 8.12: it never moves left from its initial position and never writes a blank. We know the following:

1.The start state of M is q.

2. r is the accepting state of M.

3. The tape symbols of M are 0, 1, and B (blank).

4.One of the moves of M is (q,0) = (p,1,L).

Which of the following is DEFINITELY NOT one of the pairs in the MPCP instance that we construct for the TM M and the input 001?

(a) (0r1, r)

(b) (0r, r)

(c) (0, 0)

(d) (0q1, q)

Explanation / Answer

option d is not possible as the starting state is q and for 0 it is going to q1then ager accepting 0 it is going to q which is not possible as the starting state is q. Hence it is wrong

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.