Which of the following language is decidable

Question

Consider the following languages
L₁ = {< M, q > | M is a turing machine that visits state q on some input within 10 steps}
L₂ = {< M > | M is a turing machine, |M| < 100 where |M| is number of states in machine}
Which of the following is correct?

• L₁ is decidable but L₂ is not decidable
• L₂ is decidable but L₁ is not decidable
• Both L₁ and L₂ is decidable
• Neither L₁ nor L₂ is decidable

According to Rice theorem's first part , any non-trivial property of TM is undecidable , so L1 should be undecidable , right ? Because , we can not tell whether it will not visit q on some input within 10 steps.

But , L2 is trivial property , right ?

Please correct me.

Comments

I am getting same $L_2$ is decidable and $L_1$ is undecidable

$L_1$ is semi-decidable I think.

---

Praveen Saini Sir , I got the same answer . But , these MadeEasy people confuses me every time. Can you please elaborate and explain a bit , so that I can have confidence ?

---

I read it somewhere, for checking inputs reaching at some state q within $10$ steps , then we need to check strings upto length $10$ only, so if any string out to these , reach the state q, we can get Yes. but if some string goes to infinite loop we can't say the No part. so I think L1 is r.e.

Answer 1

Both are non-trivial properties. But Rice's theorem does not say anything about properties of TM. It says about properties of language of TM or about properties of r.e. set. So, it is not applicable to given question as here it talks about TM and not its language. 

L2 is easily decidable. We can just count the no. of states in the TM description. This is similar to counting the no. of lines in a given C code. 

L1 looks semi-decidable. But it is also decidable. With one move (step) a TM can read only 1 input letter. So, in 10 steps the maximum input a TM can read is 10 letters. So, to decide the problem just simulate the given TM on all inputs of length 10 for up to 10 steps. If the TM visits state $q$ on any of them we have answer "yes" and otherwise we have answer "no". No chance of an infinite lop here. 

Comments

Got it.  :)