# Rice's Theorem: implication of having an undecidable property

I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply.

But then what? If a set of Turing machines have an undecidable property, is the language itself necessarily undecidable? Or only if you can find a reduction from a known-undecidable machine is the language undecidable?

What does it really say about a language if it has an undecidable property? Are machines that recognize that language undecidable?

• Turing machine, not "turning machine". Named after Alan Turing. – David Richerby Sep 27 '14 at 20:36

An undecidable property $\pi$ of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying $\pi$. We identify the property with the language of encodings of Turing machines satisfying the property.

The fact that a language is undecidable just means that no Turing machine decides the language — this is the definition of undecidability. In particular, no machines recognize the language, assuming recognize means decide; a machine $T$ decides a language $L$ if $T$ terminates on all inputs, on inputs $x \in L$ returns $1$, and on inputs $x \notin L$ returns $0$. A machine cannot be undecidable, only a language can be undecidable.

• Ok thank that helps me clear up me confusing languages and machines. Let me ask a follow up question: If a language has an undecidable property, then that doesn't 100% mean the language itself is undecidable, correct? – Daniel Baughman Sep 27 '14 at 20:19
• Languages cannot have undecidable properties, since you cannot give the language as an input to a program, since it is an infinite object. – Yuval Filmus Sep 27 '14 at 20:20

You are talking about two things here. Consider a non-trivial property $P$ of languages. $P$ can be anything, for instance, does the language contain a string of prime length or not.

Now there are a set of Turing Machines whose languages have this property $P$. Let,

$$S = \{\langle M\rangle \mid\text{ Language of M satisfies }P\}\,.$$

Now, Rice's Theorem says that $S$ is undecidable. This means that you cannot build a decider that takes the description of a Turing Machine and tells whether the language of the input machine has a particular non trivial property. It does NOT say that for any $L$, ($L \in P$) $L$ is undecidable.

Consider the language $L = \{10\}$. This language $L$ is in $S$ (note that I am saying $L \in S$). Clearly, the language is decidable even though $S$ is not.

• No. Rice's Theorem says that $\{\langle M \rangle \mid \text{Turing machine }M \text{ accepts a language with property }P\}$ is undecidable. – A.Schulz Dec 17 '15 at 19:25
• What does $\langle L\rangle$ mean? – David Richerby Dec 17 '15 at 19:28
• It still seems problematic to me. What does "Language of M and satisfies P" mean? Do you mean $L(M)$ satisfies $P$? – D.W. Dec 29 '15 at 5:07