Can I apply Rice's theorem to decide decidability status of these languages?

Question

I came across these languages:

1. A Turing machine prints a specific letter.
2. 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:

1. Not all turing machine languages have specific letter, hence the property is non trivial and hence undecidable.
2. Not all turing machine languages deal with performing product of two numbers, hence this property is non trivial and hence undecidable.

Doubt 1

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?

Doubt 2

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?

Update

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?

Answer 1

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.

You are talking about a narrow Rice's theorem. In Wikipedia, it states that

Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property.

So the 2nd language is indeed undecidable by Rice's theorem. For your first language, there are two interpretations:

1. A Turing machine that when it halts, the tape content is exactly a specific letter (say $s$). In this case, the Turing machine exactly computes a function $f$ where $f(w)=s$ for any $w$, so Rice's theorem applies.

2. A Turing machine ever prints a specific letter. In this case, Rice's theorem does not apply, while the language is still undecidable.

We then can define algorithm to check if transition is reachable from the start state.

No, you can't. There being a path from the start state to the transition does not mean the transition is reachable. For example, consider the following Turing machine:

  Read a; Move right    Read a; Move left    Read a; Move right
S ------------------> A -----------------> B -----------------> C
       Write b                                    Write s

There is a path from the start state $S$ to the transition that writes $s$, but this transition is not reachable because the Turing machine writes a $b$ at the first position when switching from state $S$ to state $A$, so it will never read an $a$ at state $B$.

Hence, you have to check every path to verify if a specific transition is reachable, but that is impossible because there are infinite many paths (when cycles are involved).

Answer 2

You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties.

So what defines a semantic property?

Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, with all the internal mechanisms hidden, semantic properties are the ones you can still measure.

Applying this rule of thumb, we see that printing letters and multiplying numbers are both semantic actions (they're things a program does rather than mechanisms by which the program does it), so yes, Rice's Theorem applies, and these properties are undecidable.