[Solved]: Rice's Theorem: implication of having an undecidable property

Problem Detail: 

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?

Asked By : Daniel Baughman

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30351

3.2K people like this

 Download Related Notes/Documents