Question 1 |

Which of the following is/are undecidable?

**MSQ**Given two Turing machines M1 and M2 , decide if L(M1 ) = L(M2 ). | |

Given a Turing machine M , decide if L(M ) is regular. | |

Given a Turing machine M , decide if M accepts all strings. | |

Given a Turing machine M , decide if M takes more than 1073 steps on every string. |

Question 1 Explanation:

Question 2 |

For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.

\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}

Which one of the following options is correct?

\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}

Which one of the following options is correct?

Both L1 and L2 are decidable. | |

L1 is decidable and L2 is undecidable. | |

L1 is undecidable and L2 is decidable. | |

Both L1 and L2 are undecidable. |

Question 2 Explanation:

Question 3 |

Which of the following languages are undecidable? Note that \left \langle M \right \rangle indicates encoding of the Turing machine M.

L_1=\{\left \langle M \right \rangle|L(M)=\varnothing \}

L_2={\left \langle M,w,q \right \rangle|M on input w reaches state q in exactly 100 steps}

L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\}

L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}

L_1=\{\left \langle M \right \rangle|L(M)=\varnothing \}

L_2={\left \langle M,w,q \right \rangle|M on input w reaches state q in exactly 100 steps}

L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\}

L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}

L_1,L_3 \; and \; L_4 \; only | |

L_1 \; and \; L_3 \; only | |

L_2 \; and \; L_3 \; only | |

L_2,L_3 \; and \; L_4 \; only |

Question 3 Explanation:

Question 4 |

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether w\in L(G)

(II) Given a Turing machine M, whether L(M) is regular

(III) Given two grammars G1 and G2, whether L(G1) = L(G2)

(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.

Which one of the following statements is correct?

(I) For an unrestricted grammar G and a string w, whether w\in L(G)

(II) Given a Turing machine M, whether L(M) is regular

(III) Given two grammars G1 and G2, whether L(G1) = L(G2)

(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.

Which one of the following statements is correct?

Only I and II are undecidable | |

Only III is undecidable | |

Only II and IV are undecidable | |

Only I, II and III are undecidable |

Question 4 Explanation:

Question 5 |

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A* to B*. We say f is computable if there exists a Turning machine M which
given an input x in A*, always halts with f(x) on its tape. Let L_{f} denote the language
{x#f(x)|x\inA*}. Which of the following statements is true:

f is computable if and only if L_{f} is recursive. | |

f is computable if and only L_{f} recursively enumerable. | |

If f is computable then L_{f} is recursive, but not conversely. | |

If f is computable then L_{f} is recursively enumerable, but not conversely. |

Question 5 Explanation:

Question 6 |

Consider the following languages.

L1 = {\ltM\gt |M takes at least 2016 steps on some input},

L2 = {\ltM\gt| M takes at least 2016 steps on all inputs g} and

L3 = {\ltM|M accepts \varepsilon},

where for each Turing machine M, \ltM\gt denotes a specific encoding of M. Which one of the following is TRUE?

L1 = {\ltM\gt |M takes at least 2016 steps on some input},

L2 = {\ltM\gt| M takes at least 2016 steps on all inputs g} and

L3 = {\ltM|M accepts \varepsilon},

where for each Turing machine M, \ltM\gt denotes a specific encoding of M. Which one of the following is TRUE?

L1 is recursive and L2,L3 are notrecursive | |

L2 is recursiveand L1,L3 are notrecursive | |

L1,L2 are recursiveand L3 is notrecursive | |

L1,L2,L3 are recursive |

Question 6 Explanation:

Question 7 |

Consider the following statements.

I. The complement of every Turing decidable language is Turing decidable

II. There exists some language which is in NP but is not Turing decidable

III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

I. The complement of every Turing decidable language is Turing decidable

II. There exists some language which is in NP but is not Turing decidable

III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

Only II | |

Only III | |

Only I and II | |

Only I and III |

Question 7 Explanation:

Question 8 |

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

it may halt and accept the input | |

it may halt by changing the input | |

it may halt and reject the input | |

it may never halt |

Question 8 Explanation:

Question 9 |

Let \lt M \gt be the encoding of a Turing machine as a string over \Sigma={0,1}.

Let L = { \lt M \gt |M is a Turning machine that accepts a string of length 2014}.

Then, L is

Let L = { \lt M \gt |M is a Turning machine that accepts a string of length 2014}.

Then, L is

decidable and recursively enumerable | |

undecidable but recursively enumerable | |

undecidable and not recursively enumerable | |

decidable but not recursively enumerable |

Question 9 Explanation:

Question 10 |

Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

2. Turing recognizable languages are closed under union and complementation.

3. Turing decidable languages are closed under intersection and complementation.

4. Turing recognizable languages are closed under union and intersection.

1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.

2. Turing recognizable languages are closed under union and complementation.

3. Turing decidable languages are closed under intersection and complementation.

4. Turing recognizable languages are closed under union and intersection.

1 and 4 only | |

1 and 3 only | |

2 only | |

3 only |

Question 10 Explanation:

There are 10 questions to complete.