1
$\begingroup$

I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition.

On page 66, we have:
3.4.1. Problem: For each of the following problems involving Turing machines determine whether or not it is recursive:

(a) Given a Turing machine $M$, does it halt on the empty string?
(b) Given a Turing machine $M$, is there a string for which is halts?
(c) Given a Turing machine $M$, does it ever write symbol $\sigma$?
(d) Given a Turing machine $M$, does it ever write a symbol different from the symbol currently scanned?
(e) Given a Turing machine $M$, is $L(M)$ empty? ($L(M)$ denotes here the language accepted by the Turing machine, not decided by it.)
(f) Given a Turing machine $M$, is $L(M)$ finite?
(g) Given two Turing machines $M$ and $M'$, is $L(M)=L(M')$?
Which of the non-recursive languages above are recursively enumerable?

Now, what puzzles me about this problem is that very little of the information it provides needs to be used in order to solve it. It is easy to see that all seven items describe non-trivial properties of Turing machines (that is, they are true for some Turing machines but not others) and, according to Rice's Theorem described on page 62, this means they cannot be recursive. There is barely any need to think at all about the properties described.

It seems a little odd that the author would go through the trouble of describing several different languages in some detail, when those details barely matter. It makes me wonder if my reasoning about Rice's Theorem is correct.

So my question is: is my reasoning correct that, according to Rice's Theorem, none of these described languages are recursive?

Incidentally, I think the last question in the problem is more interesting and does require more thinking about the individual languages. However, it sounds like a very secondary question, so it still makes me wonder about my answer to the main question.

$\endgroup$
  • $\begingroup$ see rice-theorem tag for more ideas or wikipedia. the thm can seem somewhat subtle at times. suggest further discussion in Computer Science Chat. it can help to see contrary examples of decidable questions about TMs. also note that the question is really "given TM [x] and any possible input [y]..." $\endgroup$ – vzn Aug 12 '15 at 17:42
2
$\begingroup$

Rice's theorem is about non-trivial properties of partial functions. It states that if $P$ is a non-trivial property of partial functions, then no algorithm can decide, given the description of a Turing machine $M$, whether $L(M) \in P$.

Rice's theorem doesn't say anything about the operation of Turing machines. A property like "$M$ ever writes $\sigma$" is not a property of $L(M)$, and so Rice's theorem doesn't apply to it.

$\endgroup$
  • $\begingroup$ think this may be misinterpreting the exercise (but am not really clear on the exercise either). reachability of a particular state (which writes a particular symbol) is equivalent to the halting problem. $\endgroup$ – vzn Aug 12 '15 at 23:15
  • $\begingroup$ @vzn All I'm saying is that Rice's theorem doesn't apply. $\endgroup$ – Yuval Filmus Aug 13 '15 at 4:42
  • $\begingroup$ @YuvalFilmus, thanks for the very good point. However, it seems that, given what you said, Rice's Theorem still solves all problems but (c) and (d), do you agree? Therefore my original point still pretty much holds... $\endgroup$ – user118967 Oct 2 '15 at 6:12
  • $\begingroup$ @user118967 Perhaps; my point was that your description of Rice's theorem was wrong. $\endgroup$ – Yuval Filmus Oct 2 '15 at 17:20

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.