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

@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.

---

The length of string and alphabet were given here, and the length is finate hence the language should be regular righht?

someone please explain.

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

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. 

---

@Shaik Masthan sir please confirm this https://gateoverflow.in/1994/gate-cse-2014-set-2-question-35?show=354344#c354344

Thanks.

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 . 

Comments

is given languGE IN QUESTION monotonic or non monotonic property

Suppose L=   <=2014 length string
can we say run for 2014 or +1 step if accpet then halt else reject as there r finite no of <=2014 length strings

can someone suggest some genral statement for such questions

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.

 

Comments

Thanks for the crystal clear definition for Recursive , Recursively Enumerable and Not Recursively Enumeranble w.r.t. Decicable , Partially Decidable and Undecidable

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

Answer 5

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 .

Answer 6

Hope it will help.