Calicut Gate Academy Test Series | TOC Q32

Question

Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}.

Then L is

1. Recursively enumerable
2. Not Recursively enumerable
3. Recursive
4. Udecidable 

(Multiple Options May be Correct . Mark them All )

Comments

https://gateoverflow.in/1994/gate2014-2_35

Answer 1

Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}

Take UTM and run all Strings using dovetailing method till 2014 length we can say Yes when alteast one of them accept but we cannot say no since thier are infinite strings to check . so Recursively enumerable (undecidable)(i.e. We cannot say no Only say yes.)

Comments

@Anirudh

Both 1 and 4 correct :)

---

yes..

---

@Anirudh SIR , 

IF a string of length 6  goes to loop before TM finish reading then we cannot say TM can accept it or not . Is that the reason for why we can't say NO ?

Since it may fall into loop we can also say it is UNDECIDABLE . 

Correct me IF Wrong ...