Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Syntactic machine properties lie outside the scope of Rice's theorem
Statement
Properties of a machine description such as "has at most ten states" or "has an unreachable state" are not extensional language properties, so Rice's theorem does not apply to them.
Facts & Assumptions
Given: The machine-description properties "has at most ten states" and "has an unreachable state."
An extensional property must assign the same truth value to any two machines with the same recognized language, by Index sets and extensional properties of Turing-machine languages.
Rice's theorem applies only to nontrivial extensional language properties, by Every nontrivial extensional property of Turing-machine languages is undecidable.
Proof
Adjoining any number of new states with no incoming transitions leaves every existing computation unchanged. Thus the original machine and the enlarged machine recognize the same language.
Start with a three-state machine and adjoin eight unreachable states. The two machines have the same recognized language by step 1.1, but the first has at most ten states and the second has eleven. Hence the state-count property is not extensional.
For the second property, take a three-state machine whose start state moves to its accept state on one input symbol and to its reject state on the blank symbol; each of its three states is reachable. Adjoin one state with no incoming transitions. Step 1.1 again preserves the recognized language, but now exactly the enlarged machine has an unreachable state. Hence this property is not extensional either.
Since the extensionality hypothesis of [L2] fails for both properties, Rice's theorem does not speak about them.
Depends on
Used by
Dependency tree · two levels
7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- EECS 376 Course Notes, Part 6: Computability (standard reference, not scraped)
- MIT 6.045J / 18.400J, Lecture 9: Mapping Reducibility and Rice's Theorem (standard reference, not scraped)