How 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.
Recognizable extensional properties are positively witnessed by finite information
Statement
Let be an extensional property of recognizable languages, and assume that its index set is recognizable. If is recognizable, then there exists a finite set such that every recognizable language with also belongs to .
Facts & Assumptions
Given: An extensional property with recognizable index set, and a recognizable language .
By Index sets and extensional properties of Turing-machine languages, membership in depends only on the recognized language, so the property can be viewed through any recognizable presentation of the same language.
The language is recognizable but undecidable, by The Turing-machine acceptance problem is recognizable and The Turing-machine acceptance problem is undecidable. A language is decidable if and only if it and its complement are both recognizable, by A language is decidable if and only if it and its complement are recognizable.
Machine descriptions have a fixed effective coding, and contains exactly the codes of accepting machine-input pairs, by A fixed effective binary encoding of deterministic one-tape Turing machines and The Turing-machine acceptance problem .
Proof
By [L2], is not recognizable: otherwise both and its complement would be recognizable and hence would be decidable.
Choose a recognizer for , and let be its finite input alphabet. Dovetail the recognizer on the words of in a fixed length-lexicographic order, outputting each newly accepted word once. This gives an effective enumeration of by finite stages with .
Suppose for contradiction that no finite subset of belongs to . For each binary word , effectively construct a recognizer that, on its own input , simulates the stage enumeration from step 1.2 and the recognizer for on in lockstep. It accepts if appears in the stage enumeration before the latter recognizer accepts, and otherwise continues forever. The coding in [L3] makes total and computable. If then ; if then for the finite stage at which that simulation stops admitting new words.
A recognizer for could therefore recognize : on input , compute and run the index-set recognizer on it. This contradicts step 1.1. Hence there is a finite set with .
Let be recognizable with , and suppose for contradiction that . For each binary word , effectively build a recognizer that accepts every word of and, if the recognizer for accepts , also simulates a fixed recognizer for . Then gives , while gives . As in step 3.1, the total computable map and the recognizer for would recognize , contradicting step 1.1. Therefore every such belongs to , and is the required finite positive witness.
Depends on
- Index sets and extensional properties of Turing-machine languages
- A fixed effective binary encoding of deterministic one-tape Turing machines
- The Turing-machine acceptance problem $A_{TM}$
- The Turing-machine acceptance problem is recognizable
- The Turing-machine acceptance problem is undecidable
- A language is decidable if and only if it and its complement are recognizable
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
17 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)
- Kevin Kelly, Many-one Reduction (standard reference, not scraped)