edited by
27,596 views
91 votes
91 votes

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:

  1. decidable and recursively enumerable
  2. undecidable but recursively enumerable
  3. undecidable and not recursively enumerable
  4. decidable but not recursively enumerable
edited by

5 Answers

Best answer
124 votes
124 votes

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$

edited by
15 votes
15 votes

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 . 

7 votes
7 votes

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.

 

1 votes
1 votes
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:

Related questions

43 votes
43 votes
3 answers
3