edited by
15,339 views
48 votes
48 votes

Consider the following statements.

  1. The complement of every Turing decidable language is Turing decidable
  2. There exists some language which is in NP but is not Turing decidable
  3. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

  1. Only II
  2. Only III
  3. Only I and II
  4. Only I and III
edited by

7 Answers

1 votes
1 votes

Turing decidable == Recursive languages, which are closed under complementation. So, $I$ is True.

The Turing decidable (ie recursive) languages are divided into three classes:

  1. P (Polynomial time)
  2. NP (Non-deterministic polynomial time)
  3. P Space (Polynomial space)

Generally, we consider only two of these classes — P and NP.

They're subdivisions of the decidable zone, so definitely if a language is in NP or P or P space, it is decidable. $III$ is True.

 

Option D

0 votes
0 votes
Are turing decidable problems are recursive? Because if they are recursive then we can give one more explanation  for  option (A) to be true because complement of the recursive languages are also recursive and hence turing decidable.
Answer:

Related questions

26 votes
26 votes
5 answers
8
go_editor asked Feb 12, 2015
14,104 views
Consider the following routing table at an IP router:$$\begin{array}{|l|l|l|} \hline \textbf {Network No} & \textbf {Net Mask} & \textbf{Next Hop} \\\hline \text {128.96...