One Function, Many Programs? Near-Minimal Descriptions and Computational Structure
Programs computing the same function can differ in their states, operations, and memory use. Does requiring short descriptions force them to share computational structure? We separate bounds on the number of programs, the information needed to reconstruct one source from another, and the relations shared by their executions. Classical prefix coding bounds both number and reconstruction cost for programs producing a common finite output. For whole functions, write k for the shortest program length and δ ≥ 0 for the allowed excess. If the function is total, the number of programs of length at most k + δ is bounded by 2^δ times a fixed polynomial in k + δ + 2, without certification. If a fixed, sound, computably enumerable equivalence relation certifies that two near-shortest programs compute the same function, either source can be reconstructed from the other with at most δ + O(log(k + δ + 2)) bits. This reconstruction result also covers partial functions; the unrestricted pairwise bound remains unresolved here. These bounds limit the number of possible structural classes but do not identify their execution relations. Minimal linear filters and selected nonlinear realizations admit structural uniqueness under their respective assumptions, whereas optimal multiplication chains can have different dependency graphs. The remaining task is to determine which shared structures follow from a specified economy criterion and realization class. Partial invariants can constrain this comparison without supplying a complete classification. Lean checks finite counting and coding; the full complexity bounds remain paper proofs.
Authors
- Giulio Ruffini (ORCID: https://orcid.org/0000-0003-3084-0177)
Institutions
- Neuroelectrics Barcelona SLU (Spain) (ES)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.5281/zenodo.24281535
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- preprint