Question

3. Let L-{(M, q》 | M is a Turing machine and q is a state in M such that: there is at least one input string w such that M executed on w enters state q). Side note: In the real world, you can think of this as a question about finding "dead code" in a program. The question is: for a given line of code in your program, is there an input that will make the program execute that line? (a) 5 marks Prove that L is undecidable. (b) 4 marks] Prove that L is recognizable.

Answer 1

3.

a)

Here we have to find whether M enters q on w,

So let us assume q as the halting state of M, now we can reduce L to Halting problem of turing machine( i.e language HALT_TM).

let us design a turing machine M1 such that:

1. on input <M,w> if M halts on w, then M1 enters enters q on input w

2. on input <M,w> if M does not halt on w, then M1 does not enter q on input w

And as we know halting problem is undecidable, so L also undecidable.

b)

here from the above design of M1 we can define

1. on input <M,w> if M halts on w, then M1 enters enters q on input w

2. on input <M,w> if M does not halt on w, then M1 does not enter q on input w and ends in looping.

So L is not Turing decidable, but turing recognizable.