Turing machine

Question

REC, RE or NOT RE ?

L = {<M> | M is a TM and |<M>| >= 5}

Comments

yes REC . because it is property of TM

not language

---

if binary encoding of TM is used, then above language is simply,

L={w |wϵ(0+1)* and |w|>=5}, which is regular and hence decidable, hence recursive, and hence recursively enumerable.

P.S: it does not matter what is language recognized by TM or whether TM is halting or not

---

difference between simple and binary encoding??

Answer 1

It's REC. more strict answer is more better.

REC  $\rightarrow$  There is a TM $M2$ which can decide this Language as follows :

M2 takes each string in this Language one by one and checks if the length of <M> is more than 5 if yes it halts and accepts and if not then it halts and rejects, Therefore we have a Halting Turing Machine M2 which can decide this language.

-- <M> is the binary encoding of the TM and |<M>| represents the length of M's encoding.

Comments

the TM which is deciding the language must Halt, that is what I said.. the TM which is given in the encoding may or may not halt

---

@Shivansh,

i was also talking about the TM which is given in encoding.

the TM which is deciding the language is definately a halting TM because given language is regular

---

ohh..