Rice's theorem: Question bank — Coding deep dive

Before we start, one shared vocabulary reminder so no symbol is used unexplained:

Here, $⟨ M ⟩$ means "the encoded description (source code) of machine $M$ ", and $L (M)$ means "the language $M$ recognizes". See Turing Machines and Recursive vs Recursively Enumerable languages if either feels shaky.

True or false — justify

Non-trivial semantic properties are always undecidable

True — that is exactly Rice's theorem. The reduction from [[A_TM and undecidability|

A_{T M}

]] builds a gadget that flips between a YES-language and

\emptyset

, and non-triviality guarantees both worlds exist.

Every undecidable language property is non-trivial

False — this is the (invalid) converse. Rice only runs one direction: non-trivial ⇒ undecidable. Trivial properties exist but they are decidable, so undecidability does not force non-triviality.

"Does

M

have exactly 10 states?" is undecidable by Rice

False — this is syntactic: two machines with identical languages can have different state counts, so it does not depend on

L (M)

. You just count states in

⟨ M ⟩

→ decidable.

If a property is trivial, its language

L_{P}

is decidable

True — a trivial property gives a constant answer ("yes for all r.e." or "no for all r.e."), so a decider that ignores its input and prints that constant works.

Rice's theorem proves the property

P

is not even r.e.

False — Rice only claims undecidable (not recursive). Whether

L_{P}

is recognizable is a finer, separate question answered by Rice–Shapiro or direct analysis.

L (M) \neq = \emptyset

" is undecidable but recognizable

True — it is a non-trivial semantic property (undecidable by Rice), yet you can dovetail a search: run

M

on all strings in parallel and accept the moment any accepts. So it is r.e. but not recursive.

Rice's theorem is a special case of the Halting Problem

False — it is the reverse: Rice is a generalization. Halting is one behavioural property; Rice says every non-trivial behavioural property is at least as hard, by reducing halting into each one.

The set of all r.e. languages having some property must itself be r.e. for Rice to apply

False — Rice makes no r.e. requirement on

P

at all. It only needs

P

to be a set of r.e. languages that is non-trivial as a property; nothing about

P

's own decidability is assumed.

Spot the error

L (M)

is regular is a syntactic property, so Rice does not apply."

Error: regularity is a fact about the language

L (M)

, not the code — it is semantic. It is non-trivial (

\emptyset

is regular,

{0^{n} 1^{n}}

is not), so Rice does apply and it is undecidable.

P

is non-trivial because I found a machine

M

with

L (M) \in P

Error: one witness is not enough. Non-triviality needs a YES-language and a NO-language. Only exhibiting the YES side leaves open that every r.e. language has

P

(trivial-true).

"The gadget

G_{M, w}

decides halting, contradiction, so

P

is undecidable."

Error:

G_{M, w}

does not decide anything — it is the transformed input. The contradiction comes from the assumed decider

R

for

L_{P}

applied to

⟨ G_{M, w} ⟩

; the gadget only encodes the halting question into a property question (Mapping reductions).

"Since

\emptyset \in P

here, Rice cannot be used."

Error: whether

\emptyset

has

P

is irrelevant to whether Rice applies. If

\emptyset \in P

, prove undecidability for the complement property

\overset{ˉ}{P}

instead — deciding

P

would decide

\overset{ˉ}{P}

, so it is symmetric.

"Rice proves everything about a TM's behaviour is undecidable."

Error: only non-trivial semantic questions. "Does

M

accept something or reject-or-loop on everything with the same answer for all machines?" — trivial questions and structural questions are outside Rice and are often decidable.

P = {\emptyset}

is trivial because it names only one language."

Error: 'trivial' is not about how many languages are listed — it is about whether the YES/NO split is empty on one side.

{\emptyset}

has

\emptyset

as a YES-witness and

Σ^{*}

as a NO-witness, so it is non-trivial and undecidable.

Why questions

Why does the reduction require a YES-witness language

L (M_{P}) \in P

Because the gadget must be able to enter a "has property" world when

M

accepts

w

. Without a target language that actually possesses

P

, there is nothing to switch into and the flip fails.

Why is

\emptyset

used as the "no" baseline in the standard proof?

When

M

never accepts

w

, the gadget's first stage loops forever, so it accepts nothing — its language is

\emptyset

. Assuming

\emptyset \in / P

makes that the guaranteed NO-world, giving a clean flip: property

⟺

M

accepts

w

Why does the gadget run

M

w

before looking at its own input

x

So that reaching the useful behaviour is gated on

M

accepting

w

. If

M

never accepts, the gadget is stuck and accepts nothing; only if

M

accepts does the gadget go on to mimic

M_{P}

and inherit

L (M_{P}) \in P

Why does non-triviality being false collapse the whole proof?

A trivial property has only one world (all-yes or all-no), so the gadget cannot flip its language between

P

and not-

P

. With no flip there is no encoding of halting, and indeed the trivial property is genuinely decidable by a constant answer.

Why can't we fix syntactic properties by "just applying Rice anyway"?

Because Rice's hypothesis literally demands the property depend only on

L (M)

. Syntactic properties violate this: two machines with equal languages can disagree on the property, so the theorem's premise is not met.

Edge cases

P = \emptyset

(no r.e. language has the property) decidable?

Yes — it is one of the two excluded trivial cases. The decider always answers "no", since by assumption no machine's language is in

P

P = {all r.e. languages}

decidable?

Yes — the other trivial case. Every r.e. language qualifies, so the decider always answers "yes".

Is "does

M

accept the specific string 01?" decidable?

No — it is non-trivial semantic (

Σ^{*}

contains 01 and is a YES-witness;

\emptyset

is a NO-witness). By Rice it is undecidable, even though it feels like a single concrete check.

Is "does

M

ever write a blank symbol on its tape?" decidable by Rice?

Rice says nothing — it is syntactic/operational (about the machine's runtime steps, not

L (M)

). Whether it is decidable is a separate analysis; Rice simply does not classify it.

If both

M_{yes}

and

M_{no}

recognize the same language, is

P

still non-trivial?

No — non-triviality needs two different languages, one in

P

and one out. Same language means same property value, so you have failed to exhibit a genuine split.

Can a non-trivial semantic property ever be co-r.e. instead of r.e.?

Yes — e.g. "

L (M) = \emptyset

" (

E_{T M}

) is co-r.e. but still undecidable. Rice fixes only the undecidability; the r.e./co-r.e. side is a finer distinction it leaves open.

Does Rice apply to properties of deciders only, or all Turing machines?

All Turing machines that recognize r.e. languages — the property is about

L (M)

, and every TM defines an r.e. language. Restricting to deciders is unnecessary and would change the setting.

Connections

Halting Problem — the seed reduced into every non-trivial property.
A_TM and undecidability — the base undecidable language.
Mapping reductions — why the gadget "transforms input", never "decides".
Recursive vs Recursively Enumerable languages — undecidable ≠ non-r.e.
Rice-Shapiro theorem — the finer tool for recognizability.
Turing Machines — the model underneath $L (M)$ and $⟨ M ⟩$ .