# Is $L=\{\langle M \rangle|M$ makes more than 10 steps on some input$\}$ decidable?

I want to show that it satisfies Rice's theorem:

(i) $L$ is non-trivial, since $\langle M\rangle \notin L$ where $L(M)=\emptyset$, as $M$ halts/rejects any input string in the first step.

(ii) if $L(M_1)=L(M_2)$ where $M_1$ and $M_2$ are turing machines, then $M_1$ makes more than 10 steps on some input iff $M_2$ makes more than 10 steps on some input.

I'm not sure if the second condition is true, and if so, why?

I know that you can always create redundant states/transitions by moving the read-write head go back and forth without changing anything, thus increasing the number of steps on a given input but giving the same outcome. But I'm not sure if you can always "shorten" a turing machine.

• Would it be possible to have a stackexchange site dedicated to Turing machines? It would be computationally complete. – Andrej Bauer Jun 14 '17 at 12:16

• Okay, if I can't use Rice's theorem, what can I do to prove $L$ is decidable (or undecidable)? I tried to build a turing machine that recognizes $L$, but I can't make it into a decider. – Sid Caroline Jun 14 '17 at 12:02
• Yes, the second condition requires that for any turing machines $M_1$, $M_2$ such that $L(M_1)=L(M_2)$, $\langle M_1\rangle \in L$ if and only if $\langle M_2\rangle \in L$ – Sid Caroline Jun 14 '17 at 12:10