Alphabeta MathNondeterministic Recursive Padding and Time Separation
About this page
Pipeline-generated
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.
1 · Prerequisites
Combinatorics
Computability Theory
Real Analysis
2 · Logical flowchart
3 · Items
Definition
Nondeterministic acceptance time and exact clocks
Lemma
Linear acceptance-time simulation on two tapes
Lemma
Prefix program codes admit linear nondeterministic universal simulation
Lemma
Time-controlled self-reference for nondeterministic machines
Lemma
Clocks, cutoffs, and finite unions preserve nondeterministic time bounds
Lemma
No recursive bound covers all recursive unary languages
Theorem
Nondeterministic recursive-padding separation
Sources
- Seiferas, Fischer, and Meyer, pp. 147-148
- Seiferas, Fischer, and Meyer, Lemma 3, pp. 149-150
- Seiferas, Fischer, and Meyer, coding conditions (1)-(3), p. 152
- Seiferas, Fischer, and Meyer, Lemma 6, p. 152
- Seiferas, Fischer, and Meyer, Lemma 1 and clock discussion, pp. 148-149
- Seiferas, Fischer, and Meyer, Corollary 2.1, p. 148
- Seiferas, Fischer, and Meyer, Theorem 4 and Corollary 4.1, pp. 152-155
- Kabanets, CMPT 710 Lecture 10, Theorem 2
- Vadhan, CS221 Lecture 6, Theorem 6