Question

L={<M> | M is a turing machine and it takes less than 481 steps on some input>

decidable or R.E??

i think it is decidable..just confirm it pls

Comments

yes it is

---

thansk thor..

the reason is this only that we will run for 481 steos,if it halts then yes,not halts then NO

---

u r right

---

I did not get it that how to check for decidability here. Kindly explain.

---

I think it is undecidable, let L is RE language that can be accepted by TM. Let W belongs to L and if we input this to TM, it will will definately tell, the given W is present in language. let W be a string which is not in L. If we give this to TM, it will complete all its steps but it is not guaranteed that TM will tell given W is not in L. Hence not decidable.

TM halting problem which is undecidable can be converted to the above problem, so by reducibility property the above problem is undecidable.

Correct me If iam wrong.

---

@Anil Actually we need to run it till 481 steps only. If it halted before 481 steps, it is not part of given language. If not halted that means it has actually covered 481 steps and hence part of our language. Here we need to check only for string less than length 481.
You can go through this Kiran Sir's video.:https://www.youtube.com/watch?v=t6UHuxNcBOU