1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Would it be possible to have a stackexchange site dedicated to Turing machines? It would be computationally complete. $\endgroup$ – Andrej Bauer Jun 14 '17 at 12:16
2
$\begingroup$

Your first statement is true. The second is not true. You can construct infinetly many TMs accepting the same language by introducing redundant states and transitions (as you already mentioned). "Minimizing" a TM has nothing to do with the second statement since two machines accepting the same language do not have to be identical and minimizing a TM gives you another machine while you compare M1 and M2.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Sid Caroline Jun 14 '17 at 12:02
  • $\begingroup$ Do you really understand the Rice's theorem and know how to use it? Isn't your first statement enough? $\endgroup$ – fade2black Jun 14 '17 at 12:08
  • $\begingroup$ 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$ $\endgroup$ – Sid Caroline Jun 14 '17 at 12:10
  • $\begingroup$ cs.stackexchange.com/a/13514/72943 $\endgroup$ – fade2black Jun 14 '17 at 12:12
0
$\begingroup$

The answer to your question is yes.

In 10 steps the Turing machine can consider at most 10 symbols, the set of strings of 10 symbols is finite. You can check each of them to see if the machine is still running after 10 steps in finite time.

Be careful, Rice's theorem talks about properties of the language accepted by $M$, not directly $M$'s behaviour.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.