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.
Problem in Papadimitriou's Computational Complexity seems odd
complexity theory;turing machines;undecidability;semi decidability