Foundations — Rice's theorem

This is the prerequisite toolbox for the main topic. We define each symbol in plain words, draw the picture it stands for, and say why the theorem needs it — in an order where each idea rests on the one before.

0. What is a "machine" here? — the symbol $M$

Picture the tape as a strip of graph paper stretching forever in both directions, with one little arrow (the head) pointing at a cell.

Why the topic needs it. Rice's theorem is a statement about Turing machines — the model of "any program at all". See Turing Machines for the full construction. Everything downstream is a question we ask about some $M$.

1. Strings, the alphabet $\Sigma$, and ${\Sigma }^{\ast }$

Picture ${\Sigma }^{\ast }$ as an ever-growing tower: length-0 has just $\epsilon$; length-1 has $0,1$; length-2 has $00,01,10,11$; and so on forever.

Why the topic needs it. The machine's job is to look at a string and eventually say accept or not. The pool of possible inputs is ${\Sigma }^{\ast }$. Example 3 in the parent ("does $M$ accept the string 01?") is a question about one specific member of ${\Sigma }^{\ast }$.

2. What a machine accepts — the language $L(M)$

When you feed $M$ a string $x$, three things can happen:

• $M$ halts and says accept,
• $M$ halts and says reject,
• $M$ runs forever (never stops — the tape keeps scrolling).

Why the topic needs it. Rice's theorem talks about properties of $L(M)$ — the behavior set, not the rulebook. When the parent writes "$L(M)=\varnothing$" or "$L(M)$ is infinite", it is asking a question about this bucket of accepted strings.

3. The empty set $\varnothing$ and other special languages

Contrast three landmark languages you will meet again and again:

Why the topic needs it. The proof's gadget flips between "$L=L(M_P)$ (has the property)" and "$L=\varnothing$ (does not)". So $\varnothing$ is not a footnote — it is one of the two worlds the whole reduction swings between.

4. Recursive vs. Recursively Enumerable — decidable vs. recognizable

This is the most important pair of words on the page. See Recursive vs Recursively Enumerable languages.

Why the topic needs it. The whole theorem is the single word "undecidable", and that word is meaningless until you own this pair.

5. Naming a machine as data — the code $⟨M⟩$

Picture a program's source code saved as a text file: the running program is $M$; the file's contents are $⟨M⟩$. You can also bundle several things: $⟨M,w⟩$ is one string holding both a machine's code and an input string $w$.

Why the topic needs it. A checker is itself a machine; its input must be a string. So to ask a machine about a machine, we hand it $⟨M⟩$. The set the theorem studies is literally $L_P=\{⟨M⟩:L(M)\in P\}$ — a set of codes.

6. A property $P$ and its code-set $L_P$

Why the topic needs it. "Is property $P$ decidable?" is shorthand for "is the language $L_P$ decidable?" — because that is the concrete yes/no set a decider would have to compute.

7. Non-trivial — the one word that turns the theorem on

Why the topic needs it. Without both worlds the gadget machine has nothing to flip between, and the proof collapses. This single condition is why the trivial cases ($P=\varnothing$, $P=$ all r.e.) are the sole survivors that stay decidable.

8. Mapping reduction — the arrow ${\le }_m$

Why the topic needs it. The gadget $G_{M,w}$ in the parent is the translator $f$: it maps the input $⟨M,w⟩$ to the code $⟨G_{M,w}⟩$, and the flip $L(G_{M,w})\in P⟺M\text{ accepts }w$ is precisely $x\in A⟺f(x)\in B$.

9. The seed problems — $A_{TM}$ and Halting

Why the topic needs it. Rice does not re-prove impossibility from scratch — it borrows the known impossibility of $A_{TM}$ and spreads it, via the reduction arrow, onto every non-trivial property. $A_{TM}$ is the single fixed point everything is anchored to. (The finer refinement of "which properties are at least recognizable" lives in Rice-Shapiro theorem.)

The prerequisite map

Equipment checklist

Test yourself — cover the right side and answer out loud.

Connections

• Rice's theorem — the topic these foundations build toward.
• Turing Machines — the model $M$ lives in.
• Recursive vs Recursively Enumerable languages — the decidable/recognizable split.
• A_TM and undecidability and Halting Problem — the seed of impossibility.
• Mapping reductions — the arrow ${\le }_m$ that spreads impossibility.
• Rice-Shapiro theorem — the finer follow-up (recognizability).