Michael Schroeder · Preprint · Version 1.0 · 28 September 2026

Universal Computation With 144 Residue Classes: A One-State Linear Operator Algorithm

DOI: 10.5281/zenodo.23018009

Author ORCID: 0009-0004-3249-0195

Abstract

We construct an explicit universal one-state linear operator algorithm with 144 residue-selected rules acting on a single nonnegative integer. This reduces the modulus reported by Kaščák (1992) from 396 to 144, a decrease of 252. The construction combines arithmetic invariants that exclude unreachable branches with a quotient-parity test that selects the return operation as division finishes. Every continuing rule gives an exact nonnegative successor on its entire residue progression. We supply the complete numerical table and a Lean 4 proof of universality under explicit computable input and output encodings. The simulation realizes every unary partial recursive function and preserves nontermination. Consequently, its halting set is computably enumerable complete.

Paper and Supplement

The main paper presents the construction, worked examples, the universality proof and the complete 144-rule table. The supplement supplies the full finite inventories, model comparisons, additional proofs and resource analysis. Keep both PDFs together with their original filenames for their cross-document links.

Lean Proofs and Verification Materials

The publication package contains the main paper and supplement, one canonical numerical-data archive, one Lean formalization archive, a guide connecting the paper’s claims to their proofs, and integrity checksums.

Start with README.md in the archive. The data and Lean archives each contain reproduction instructions and manifest checkers. Fresh verification runs write their reports separately, preserving the distributed verification evidence.

Citation and file integrity

Schroeder, Michael. Universal Computation With 144 Residue Classes: A One-State Linear Operator Algorithm. Version 1.0, Zenodo, 2026. DOI: 10.5281/zenodo.23018009. Download the BibTeX citation.

The paper, supplement and ZIP on this site are byte-identical to the published Zenodo files. Download the SHA-256 checksums.

The Result and Its Formalization

The machine stores its evolving configuration in one nonnegative integer. Its residue modulo 144 selects the next affine rule. Arithmetic invariants remove unreachable branches, and a quotient-parity test selects the return operation as a division finishes. The construction uses 252 fewer residue classes than Kaščák’s reported modulus of 396, a reduction of approximately 63.6%.

Lean 4 verifies the literal numerical table, exact nonnegative successors on every continuing residue progression, the simulation, computable input and output wrappers, universality, and completeness of the computably enumerable halting set. The main introduction and the archive’s proof guide specify the formalization’s scope. Resource estimates, coefficient optimality under fixed architectural assumptions and several supplementary dynamical results are established by written proofs. The result makes no global minimality claim or claim of polynomial simulation overhead.