1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In "Update" section, I concluded we cannot apply Rice's theorem to both problems. Have you read it? Quoting from Ullman's book: "All problems about Turing machines that involve only language that TM accepts are undecidable. However, Rice's theorem does not imply that everything about TM is undecidable. For instance, questions that ask about states of TM, rather about language it accepts, could be decidable". Hence, we cannot apply Rice's theorem to both problems as they both dont talk about TM languages. Right? $\endgroup$ – anir Nov 17 at 6:43
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ [1/6] Quote from Ullman's book: "All problems about Turing machines that involve only the language that the TM accepts are undecidable. However, Rice's Theorem does not imply that everything about TM is undecidable. For instance, questions that ask about the states of TM rather that about language it accepts, could be decidable". $\endgroup$ – anir Nov 17 at 16:05
  • $\begingroup$ [2/6] What does wikipedia mean by "function" in "non-trivial property of partial functions"? A "logical meaning of computation" done by TM? Wikipedia also says: "It is important to note that Rice's theorem does not say anything about those properties of machines or programs that are not also properties of functions and languages. For example, whether a machine runs for more than 100 steps on a particular input is a decidable property, even though it is non-trivial. But, the class of computable functions that return 0 for every input, and its complement is undecidable by Rice's theorem" $\endgroup$ – anir Nov 17 at 16:05
  • $\begingroup$ [3/6] Q1. From these two examples, I feel that "function" does indeed mean "logical meaning of computation". Am I right? $\endgroup$ – anir Nov 17 at 16:05
  • $\begingroup$ [4/6] I feel first language means "there exists at least one string for which TM prints specific letter". I guess this is similar to your 2nd interpretation. But if I understand it correct, you mean to say that your 1st interpretation is "function" of TM & your 2nd interpretation is "property" of TM. Hence Rice's theorem applies to 1st one, but not to 2nd one. Right? Q2. If yes why? Or can we have more clearer way to identify what is function of TM & what is property? I feel if it talks about all inputs to TM (like $f(w)$), then its function, else its property. Is it so? $\endgroup$ – anir Nov 17 at 16:06
  • $\begingroup$ [5/6] "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).", but those cycles will have repeating behavior of reading / writing from / to tape. Q3. Dont we have to do it just once? In fact, thats the precise question I asked here in detail. Can you please have a look at it? $\endgroup$ – anir Nov 17 at 16:06

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.