Weak-Path Computational Universality of the S Combinator: A Fixed Binary-Tag Simulation with an Explicit Finite Evaluation-Order Selector
We give a constructive proof that the S combinator supports universal computation under the weak path-based notion explicitly contemplated in the Wolfram S Combinator Challenge. The construction composes a fixed period-912 Cook/Rogozhin cyclic tag source, Neary's compilation to a fixed binary tag system with deletion number 3648, a closed pure-S generated carrier grammar with structural deletion and self-delimiting appending, and a fixed 3104-state finite-control selector whose term-changing actions are native S contractions. Erasing navigation microticks leaves a genuine S-reduction path. Structural checkpoint decoding recovers every finite deterministic source-computation prefix. The result establishes weak-path/evaluation-order universality only; it does not claim universality under every reduction order or strong multiway universality. This public preprint corresponds to the solution submitted to the Wolfram S Combinator Challenge on 28 September 2026. A separate reproducibility supplement contains the frozen raw transition table, independent verification scripts, selected Lean sources, SHA-256 manifests, and project certificates.
Authors
- Manuel Jofré Asenjo
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-28
- DOI
- https://doi.org/10.5281/zenodo.23019057
- Primary Topic
- DNA and Biological Computing
- Type
- preprint