Rice's theorem

Once you know the halting problem is undecidable, you might hope it is an isolated freak and that most useful questions about programs are still answerable. Rice's theorem demolishes that hope in one sweeping stroke. It says that ANY non-trivial property of the LANGUAGE a program recognizes is undecidable. 'Does this program recognize the empty language?' 'Does it accept the string hello?' 'Is its language finite?' 'Is its language regular?' Every one of these is undecidable. Almost every interesting semantic question about programs is off the table.

Let us state it carefully so it is not over-claimed. Consider a property P of languages — a yes/no question about a set of strings, like 'is the set empty?' P is non-trivial if some recognizable language has it and some recognizable language does not (so P is neither always-yes nor always-no). Rice's theorem says: for any non-trivial property P of the recognizable languages, the problem 'given a machine M, does the language L(M) have property P?' is undecidable. The proof is a reduction from A_TM: if you could decide property P, you could rig a machine whose language has P exactly when a given (M, w) is in A_TM, deciding A_TM, which is impossible.

Two boundaries keep the theorem honest. First, the property must be about the LANGUAGE the machine recognizes, not about the machine's text — 'does M have exactly 7 states?' or 'does M's code contain the letter q?' are decidable, because you just read the code. Second, the property must be non-trivial; the always-true property ('L(M) is some recognizable language') and the always-false property are both trivially decidable. Within those guardrails, Rice's theorem is breathtakingly broad: there is no general algorithm to determine what a program's behaviour actually is.