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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs 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.