Rice's theorem

Rice's theorem

by Vlad Andries -
Number of replies: 2

Good morning,

I don't think I completely got page 58 of slides "09_undecidability.pdf". 

I got rice's theorem and it's proof but in which sense a TM cannot classify a regular language? Don't simple automatas already do that by final state? Same goes for finite and context free languages. 

I was hoping for an explanation on this matter. 

Thank you in advance!

In reply to Vlad Andries

Re: Rice's theorem

by Vishesh Goyal -
From what i understand its not about weather a language is regular or not but given coding of a turing machine M does L(M) belong to set of Regular or not. Meaning given description of a TM can we look at it and tell weather it recognizes regular language or not. And rice theorm says it cannot
In reply to Vishesh Goyal

Re: Rice's theorem

by NICOLA RANZOLIN -
From my understanding property \(P\) is defined by the statement “given the encoding of a Turing Machine \(M\), the language \(L(M)\) is a regular language”.

This is a semantic property of the machine’s behaviour, not a question about running the machine on a specific input.

Non-triviality comes from noticing that some recursively enumerable languages are regular (e.g. \(\emptyset\)), and some recursively enumerable languages are not regular (e.g. \(\{0^n1^n\}\)).

Because the property is non-trivial, Rice’s Theorem applies, and the problem is undecidable. So the issue is not whether a DFA can recognize a regular language (it can), but that you cannot decide from the source code of an arbitrary TM whether the language it recognizes is regular.