# Questions & Answers of Turing machines and Undecidability

Question No. 39

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language $\{x\;\#\;f(x)\vert x\in A^\ast\}$. Which of the following statemeant is true:

Question No. 141

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turning machine M.

Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is $\style{font-family:'Times New Roman'}{w\in L(R)}$?

II. Given context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}\phi$?

III. Given a context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}{\sum\nolimits^\ast}$ for some alphabet $\style{font-family:'Times New Roman'}\sum$?

IV. Given a Turning machine M and a string w, is $\style{font-family:'Times New Roman'}{w\in L(M)}$

Question No. 154

Consider the following languages.
$L_1$ = $\{\vert\;M\;$ \mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{some}\;\mathrm{input}$\},$
$L_2$ = $\{\vert\;M\;$ \mathrm M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{all}\;\mathrm{inputs}$\},$ and
$L_3$ = $\{\vert\;M\;$ accepts $\varepsilon\;\},$
where for each Turing machine M, $\style{font-family:'Times New Roman'}{\left\langle M\right\rangle}$ denotes a specific encoding of M. Which one of the
following is TRUE?

Question No. 120

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?

Question No. 45

Let L be a language and $\overline{)L}$ be its complement. Which one of the following is NOT a viable possibility?

Question No. 126

Let Am B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

Question No. 145

Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let

Question No. 226

Let Σ be a finite non-empty alphabet and let ${2}^{{\sum }^{*}}$ be the power set of Σ*. Which one of the following is TRUE?

Question No. 245

Which one of the following problems is undecidable?

Question No. 17

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.

Question No. 4

Assuming P ≠ NP, which of the following is TRUE?

Question No. 24

Which of the following problems are decidable?

 1) Does a given program ever produce an output? 2) If $L$ is a context-free language, then, is $\stackrel{-}{L}$ also context-free? 3) If $L$ is a regular language, then, is $\stackrel{-}{L}$ also regular? 4) If $L$ is a recursive language, then, is $\stackrel{-}{L}$ also recursive?

Question No. 8

Which of the following pairs have DIFFERENT expressive power?

Question No. 9

Which of the following is true for the language {ap | p is a prime}?

Question No. 10

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

Question No. 13

If L and  $\overline{L}$ are recursively enumerable then L is

Question No. 6

Which of the following problems is undecidable?