1 votes 1 votes 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 Theory of Computation theory-of-computation turing-machine + – Akriti sood asked Jan 15, 2017 Akriti sood 2.4k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Lucky sunda commented Jan 20, 2017 reply Follow Share I did not get it that how to check for decidability here. Kindly explain. 0 votes 0 votes AnilGoudar commented Apr 17, 2017 reply Follow Share 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. 0 votes 0 votes sks24 commented Apr 17, 2017 reply Follow Share @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 1 votes 1 votes Please log in or register to add a comment.