GATE CSE 2014 Set 2 | Question: 35

Question

Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machine}\\\text{ that accepts a string of length 2014} \right\}.$$ Then $L$ is:

• A. decidable and recursively enumerable
• B. undecidable but recursively enumerable
• C. undecidable and not recursively enumerable
• D. decidable but not recursively enumerable

Comments

We call recursively enumerable languages semi-decidable, then here why are we saying it is Recursively enumerable and undecidable?

---

@nadeshseen semi-decidable property is a kind of subset of undecidable property. If a Turing machine accepts all string present in a language but we don't know whether it halts on a string not present in the language or not, then it is semi decidable because we don't know what will happen either it accepts or rejects. Due to the fact "at least it accepts all string present in the language it is SEMI-decidable.
But if a Turing machine designed to accept strings present in a language, may or may not halt on at least one string present in the language, then we consider it as an undecidable problem because it may accept or reject in infinite time that's why it is not even semi-decidable.
This is one of the most confusing topics of computer science, kindly read it carefully...

---

What could be the answer if in the question if in the question M is a turing machine that accepts a string of length atleast 2014?

It will remain same as this still a non trivial property so according to rice theorem it will be undecidable.

Answer 1

Answer: (B)

Explanation: There are finite number of strings of length ‘2014’. So, a turing machine will take the input string of length ‘2014’ and test it.

If, input string is present in the language then turing machine will halt in final state .

But, if turing machine is unable to accept the input string then it will halt in non-final state or go in an infinite loop and never halt.
Thus, ‘L’ is undecidable and recursively enumerable .