1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Daniel Baughman Sep 27 '14 at 20:19
  • $\begingroup$ Languages cannot have undecidable properties, since you cannot give the language as an input to a program, since it is an infinite object. $\endgroup$ – Yuval Filmus Sep 27 '14 at 20:20
0
$\begingroup$

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.

Hope that clears your doubt.

$\endgroup$
  • 5
    $\begingroup$ No. Rice's Theorem says that $\{\langle M \rangle \mid \text{Turing machine }M \text{ accepts a language with property }P\}$ is undecidable. $\endgroup$ – A.Schulz Dec 17 '15 at 19:25
  • 1
    $\begingroup$ What does $\langle L\rangle$ mean? $\endgroup$ – David Richerby Dec 17 '15 at 19:28
  • $\begingroup$ The answer was horribly wrong before. Hopefully, it makes more sense now. $\endgroup$ – Divyanshu Shende Dec 28 '15 at 19:38
  • $\begingroup$ It still seems problematic to me. What does "Language of M and satisfies P" mean? Do you mean $L(M)$ satisfies $P$? $\endgroup$ – D.W. Dec 29 '15 at 5:07
  • $\begingroup$ Yes. It's supposed to mean L(M) satisfies P. Is the answer okay now? $\endgroup$ – Divyanshu Shende Feb 1 '16 at 15:31

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.