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.
Index sets and extensional properties of Turing-machine languages
Definition
Let be a class of recognizable languages over finite alphabets. Its index set is where is the chosen code of a Turing machine and is the language recognized by .
The class is an extensional machine property when Thus membership depends only on the recognized language, not on the particular machine code.
The property is nontrivial when some recognizable language belongs to and some recognizable language does not.
Depends on
Used by
- Standard semantic properties such as emptiness, finiteness, regularity, and context-freedom are undecidable Corollary
- A nontrivial extensional property admits a uniform witness machine construction Lemma
- Syntactic machine properties lie outside the scope of Rice's theorem Proposition
- Every nontrivial extensional property of Turing-machine languages is undecidable Theorem
- Recognizable extensional properties are positively witnessed by finite information Theorem
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
- H. G. Rice, Classes of Recursively Enumerable Sets and Their Decision Problems (standard reference, not scraped)
- EECS 376 Course Notes, Part 6: Computability (standard reference, not scraped)