Register

GO Classes DPP | GATE CS | Theory of Computation | Decidability

ago
50 views
1 1 vote

Suppose a language $L$ is Turing-decidable. Which statement must be true?

  1. For a string $s\notin L$, a Turing machine deciding $L$ will eventually enter a reject state.
     
  2. For $s\notin L$, there need not exist a decider that determines membership of $s$.
     
  3. For $s\notin L$, the Turing machine may enter an infinite loop.
     
  4. For $s\notin L$, the Turing machine definitely does not halt.

1 Answer

0 0 votes

A language is decidable if there exists a decider $D$ for it.

A decider must halt on every input.

Therefore:

If $s\in L$, $D$ halts and accepts.

If $s\notin L$, $D$ halts and rejects.

So for a non-member, infinite looping is not allowed.

Hence,

Answer : $\boxed{\mathrm{A}}$

ago
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

0 0 votes
1 1 answer
72
72 views
GO Classes asked 5 days ago
72 views
GO Classes DPP | GATE CS | Theory of Computation | Turing Machine
Consider, $A_{\mathrm{TM}}=\{\langle M,w\rangle\mid M\ \mathrm{is\ a\ TM\ and}\ M\ \mathrm{accepts}\ w\}$Mark all properties that are certainly true for the stated langua...
0 0 votes
1 1 answer
47
47 views
GO Classes asked 5 days ago
47 views
GO Classes DPP | GATE CS | Theory of Computation | Halting Undecidability
Which statement is INCORRECT?A universal Turing machine can simulate any Turing machine $M$ on any input for $M$. The Church Thesis states that the informal notion of an ...
1 1 vote
1 1 answer
64
64 views
GO Classes asked 5 days ago
64 views
GO Classes DPP | GATE CS | Theory of Computation | Non-RE Languages
Which statements are correct?A language is a set of words. A word is a set of symbols. Some languages cannot be recognized by any NFA. Some languages cannot be recognized...
1 1 vote
1 1 answer
63
63 views
GO Classes asked 5 days ago
63 views
GO Classes DPP | GATE CS | Theory of Computation | Halting Problem
Which statements concerning the Halting Problem are correct?The Halting Problem is undecidable. The Halting Problem is semi-decidable. The Halting Problem simply refers t...