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.

$\endgroup$
1
  • 1
    $\begingroup$ Would it be possible to have a stackexchange site dedicated to Turing machines? It would be computationally complete. $\endgroup$ Commented Jun 14, 2017 at 12:16

2 Answers 2

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.

$\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$ Commented Jun 14, 2017 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
    Commented Jun 14, 2017 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$ Commented Jun 14, 2017 at 12:10
  • $\begingroup$ cs.stackexchange.com/a/13514/72943 $\endgroup$
    – fade2black
    Commented Jun 14, 2017 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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