# Turing machine halting in at least 100 steps on all inputs

L = {< M > $\mid$ L(M) = M halts on all inputs in atleast 100 steps }.

Answer to this question is given undecidable in my book without any explanation but I think it is decidable.

$\overline{L}$ = {< M > $\mid$ L(M) = M halts on some input in atmost 100 steps }

For the above language, we can feed strings of length ranging from 1-100 (finite amount of strings) and run Turing machine for finite amount of steps (100) on each string and check if at least one of them halts in atmost 100 steps.

So, as the complement of L is recursive, L should also be recursive and decidable according to me.

Where am I going wrong ?

• To check if there exists an input which halts in atmost 100 steps, it is enough to check only strings of length upto 100 I guess. For strings of length greater than 100, we can check if it's prefix of length 100 halts in atmost 100 steps or not. – Rajesh R Jan 25 '18 at 5:50
• Your $\overline{L}$ doesn't include machines which don't halt at all on some input, so it isn't really the complement of $L$. – rici Jan 25 '18 at 6:07
• @rici, Ok. Even if I include it, we check only finite amount of strings for finite amount of steps right ? So shouldn't it be decidable? – Rajesh R Jan 25 '18 at 6:16
• No. The complement of $L$ contains machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say) and machines which don't halt for some input. The second part requires a solution to the halting problem. How do you know that a machine doesn't halt ever for some input? – rici Jan 25 '18 at 6:18
• Right. Which is what your book says, no? – rici Jan 25 '18 at 6:21

You have not correctly computed $\overline{L}$. It contains
The second part requires a solution to the halting problem, so $\overline{L}$ is not decidable (nor recursively enumerable).