1
$\begingroup$

I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

They say that the above theorem is per Rice theorem which states that:

"Every nontrivial property of the RE languages is undecidable."

How are these two statements equivalent? The former deals only problems while the later deals with non trivial property.

$\endgroup$
3
  • 2
    $\begingroup$ Problems and properties (and languages) are the same thing. Also, Hopcroft et al. forgot to mention nontriviality, or perhaps assumed it was obvious. $\endgroup$ – Yuval Filmus May 8 '20 at 21:12
  • $\begingroup$ @YuvalFilmus Now that you say so, here problems and property (both with respect to RE languages) have RE languages in them and they are same (thanks for the help), Also, Hopcroft et al. forgot to mention nontriviality, or perhaps assumed it was obvious Do you mean that about mentioning nontrivial before problems in the statement highlighted in gray (above in the question body) by the authors? $\endgroup$ – Abhishek Ghosh May 9 '20 at 7:30
  • 1
    $\begingroup$ Right, the “obvious” bit refers to nontriviality. $\endgroup$ – Yuval Filmus May 9 '20 at 7:48
1
$\begingroup$

There are a few keywords in the excerpt from the said text book - non-trivial, problem, property.

Now what is a problem, assuming we are not dealing with combinatorial optimization problems,i.e. we are dealing with only questions which have an YES or NO answer to them. When you ask a YES or NO question to an input string if the answer is YES you place it in a set $L$ and if the answer is NO you just discard it. Now this set $L$ is the language or the problem. It contains all those strings which which satisfy our YES or NO question.

All non-trival problems about Turing machines that involve only the language that the TM accepts are undecidable

Here the author is talking about YES or NO questions (with respect to Turing machines) only involing the language that the Turing machine accepts,i.e. the Recursively Enumerable language(RE), which means that our "problem" set shall contain only RE languages. Now a trivial problem is one in which the our YES or NO question is either satisfied by all input or satisfied by none of the input. So a non-trivial problem is one which is neither empty nor it has all possible inputs.

Rice Theorem: "Every nontrivial property of the RE languages is undecidable."

Property of RE languages is a set of RE languages having the said property.

Non-trivial property: The property is either satisfied by all concerned languages or by none.

So "nontrivial property of the RE languages" becomes the set of RE languages and it is neither empty nor it has all possible RE languages.

By the above argument we can say that the two statements are equivalent.

(In fact property and problem are the same thing, they both are set of strings after all. Now we might think that property is a set of languages, although while it is true, it is inconvenient to represent languages in a set(as languages can be infinitely long), rather what is done is instead of the language , we represent the corresponding Turing Machine with a suitable encoding)

$\endgroup$

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.