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

There are only a finite number of strings of length $2014$. So, we can give all those strings to $TM$ simulating each string for $1$ step, then $2$ step and so on (dovetailing), and if the $TM$ accepts any of them ("yes" case of $TM$), we can say "yes". So, $L$ is recursively enumerable.

(If the $TM$ doesn't accept any string of length $2014$, it can go to an infinite loop ("no" case of $TM$), and hence we can't say the method is decidable).

Now, to prove whether the problem is decidable or not we can make use of Rice's theorem. Rice's theorem (I) states that any non-trivial property of $L(TM)$ is undecidable. $L(TM)$ has a string of length $2014$ is a non-trivial property as there are $TM$s whose language contains such a string and there are $TM$s whose language doesn't have such a string. So, the given problem is undecidable.
http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

Correct Answer: $B$

Comments

What is “better” is different for different people 😀 But if you are seeing this question, there is not even one other answer which is even “correct”. Making statements to justify a given answer key – is not “Answer”. Once you understand Rice’s theorem or decidability topic you’ll realize that.

---

Here its just said that TM accepts a string of length 2014, it is not said that it only accepts string of length 2014, so accordingly does that mean it may accepts  string having length other than 2014

---

Thanks @Arjun Sir for the great explanation :)

@Chaitanya Kale Maybe or may not be. That’s why it is undecidable. 

Answer 2

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 . 

Answer 3

There will be 2 case for the string of length 2014 :

Either,

1) It will be halt on final state i.e. accepted.

or else,

2) It will halt on non-final state or go on a loop.
 

So this is a partially decidable language.

If 100% decidable then Recursive

If partially decidable then Recursively enumerable

If 100% not decidable then not Recursively enumerable

Hence it is Partially decidable(Undecidable) and Recursively Enumerable.

 

Answer 4

String can be of length 1,2,3,2014...N but we can never be sure that TM will ever halt on that given input or not hence it is undecidable