Turing Machine: RE, REC and Undecidability GATE 2014 Question #9998 with Solution

GATE 2014 · session-3

Theory of ComputationTuring Machine: RE, REC and UndecidabilitymediumMCQ2 marks

Consider the decision problem 2CNFSAT defined as follows: {Φ | Φ is a satisfiable propositional formula in CNF with at most two literals per clause} For example, Φ=(x₁∨x₂)∧(x₁∨¬x₃)∧(x₂∨x₄) is a Boolean formula and is in 2CNFSAT. The decision problem 2CNFSAT is

ANP-Complete.Bsolvable in polynomial time by reduction to directed graph reachability.Csolvable in constant time since any input instance is satisfiable.DNP-hard, but not NP-complete.

Save your progress

Related Theory of Computation PYQs

GATE 2014 · Set-2

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…

GATE 2014 · Set-3

Let Σ be a finite non-empty alphabet and let 2^(Σ*) be the power set of Σ*. Which of the following is TRUE?

GATE 2014 · Set-2

Which of the following decision problems regarding formal languages is UNDECIDABLE?

GATE 2014 · Set-2

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…

GATE 2014 · Set-2

Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B.Which one of the followi…

GATE 2014 · Set-3

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

Saved progressKeep answers, mock results and completion history across devices.

Adaptive practiceGet questions matched to your recent accuracy and difficulty level.

Bookmarks and notesBuild a personal revision list and record why a question was difficult.

Performance insightsSee weak subjects, accuracy trends, streaks and exam readiness.

Related Theory of Computation PYQs

Turn practice into measurable progress