# Prove that this language is decidable or undecidable

Is the following language decidable?

L = {(M) : M performs at least 100 steps on every accepted input.}

I tried to use reduction from the halting problem, but still no dice.

Yes, it is decidable. There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.

• Next time, consider waiting until the OP reveals what effort, if any, they expended on solving the problem themselves. – Yuval Filmus Feb 24 '17 at 3:17