Theorem 5.1 — unrestricted abstract realisability
ProvedCallCountPOPBR.Supplement.theorem_5_1p2o-gran-per-chapterp2o-plan-paperp2o-v1recursive-algorithmstheoretical-computer-science
An integer sequence is the invocation-count sequence of an abstract decreasing-argument recursive specification with unrestricted branching if and only if
Repeated immediate calls are permitted, and the specification need not be computable.
Differences from the source:
- encoding: an abstract rule may repeatedly call any smaller input → a list of smaller natural-number arguments, whose recursively defined natural count is cast to an integer; reason: lists retain multiplicity and order while representing exactly the source model
Preamble
import Mathlib import Definitions.Def_CallCountPOPBR_Supplement_DecSpec set_option autoImplicit false
Formal statement
namespace CallCountPOPBR.Supplement
/-- **Theorem 5.1 (Unrestricted abstract realisability).** Swain, *Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and
Partial-Observation Reconstruction*, STOC 2027 submission (manuscript sha256 79135884…), Theorem 5.1, p.9: "A sequence of
integers (c_n)_{n≥0} is realisable by an abstract decreasing-argument recursive specification with
unrestricted branching if and only if c_0 = 1 and c_n ≥ 1 for all n."
Realisable: `c n` is the call count `s.count n` of some decreasing-argument specification `s`
(no bound on the number of calls). -/
theorem theorem_5_1 (c : ℕ → ℤ) :
(∃ s : DecSpec, ∀ n, c n = (s.count n : ℤ)) ↔ (c 0 = 1 ∧ ∀ n, 1 ≤ c n) := by sorry
end CallCountPOPBR.Supplement
Source
Swain, Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation Reconstruction, STOC 2027 submission (manuscript sha256 79135884…), Theorem 5.1, p.9