I came across these languages:
- A Turing machine prints a specific letter.
- A Turing machine computes the products of two numbers
I was guessing whether I can apply Rice's theorem to decide upon above are decidable or undecidable, something like this:
- Not all turing machine languages have specific letter, hence the property is non trivial and hence undecidable.
- Not all turing machine languages deal with performing product of two numbers, hence this property is non trivial and hence undecidable.
Doubt is that, Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept. I tried to interpret given problems as if they are talking about the languages accepted by those Turing machines, so that I can apply Rice's theorem to decide their decidability status. Am I correct with this?
If we have specification of TM along with its transition functions, in some encoded format, cant we prepare an algorithm to parse that encoding and tell whether the TM ever prints specific letter? The encoding must contain a transition which prints desired letter. We then can define algorithm to check if transition is reachable from the start state. If yes, then TM prints desired letter, and hence decidable. But this contradicts with earlier answers that "whether TM prints a specific letter" is undecidable. What is correct here?
After a lot of thinking, I feel we cant apply Rice's theorem here, since both problems put describe nature of output produced by TM, that is on content of tape after TM has processed original content of tape. But the language accepted by TM is content of tape, before TM starts processing. So both problems dont talk about language of TM and hence we cannot apply Rice's theorem to both problems. Am I correct with this?