Question

{ <N> : L(M) contains a string starting with a). Rice's theorem can be F 20, L used to prove that LD. T L(M2) >. Rice's theorem can be used to prove T F 21. L that L D. <M,, M2> L(M,) 22. L-( <M,M> : L(M) = L(M2) }, and R is a mapping reduction function from H to L. It is possible that R retur a TM. T F ns <M#>, where M # is the string encoding of T 23. F M# is defined below, where M is any TM, x is the contents of M's input tape, Σ={a,b,c), and w is any string in Σ.. 1. Accept if x e anbnen 2. Overwrite x with w on the input tape 3. Simulate M on w. 4. Accept

Answer 1

20. True because the property of string starting with 'a' is non-trivial property which can be recognized by Turing machine and hence as per Rice theorem, language L with non-trivial property P is undecidable .

21. False, because the property that L(M₁) = L(M₂) is not the property of language but the property of Turing mahine and hence Rice theorem cannot be applied here.

22. False because reduction from H to L will reduce the input instance of halting problem to input instance of L which should be in the form of <M₁,M₂> but this is not the case here.

23. True because if M halts on w then M_# will accept every input including aⁿbⁿcⁿ . In other words if M halts on w then $L(M_\#) = \Sigma^*$ which is always context free language.

Please comment for any clarification.