Computer Sciences > GATE 2015 SET-2 > Turing Machines
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?
Correct : d
Similar Questions
For a Turing machine M, denotes an encoding of M. Consider the following two languages.L1 = { | M takes more than 2021 steps on all inputs}L2 = { | M takes mor...
Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let L = {< M > | M is a Turing machine that accepts a string of length 2014}. Then, L...
A palindrome is a word that reads the same forwards and backwards. In a game
of words, a player has the following two plates painted with letters.
From...
Total Unique Visitors
Loading......