Rice's theorem

Re: Rice's theorem

by NICOLA RANZOLIN -
Number of replies: 0
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.