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$
1
  • $\begingroup$ Turing machine, not "turning machine". Named after Alan Turing. $\endgroup$ Commented Sep 27, 2014 at 20:36

2 Answers 2

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$
2
  • $\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$ Commented Sep 27, 2014 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$ Commented Sep 27, 2014 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$
6
  • 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
    Commented Dec 17, 2015 at 19:25
  • 1
    $\begingroup$ What does $\langle L\rangle$ mean? $\endgroup$ Commented Dec 17, 2015 at 19:28
  • $\begingroup$ The answer was horribly wrong before. Hopefully, it makes more sense now. $\endgroup$ Commented Dec 28, 2015 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.
    Commented Dec 29, 2015 at 5:07
  • $\begingroup$ Yes. It's supposed to mean L(M) satisfies P. Is the answer okay now? $\endgroup$ Commented Feb 1, 2016 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.