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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

One Function, Many Programs? Near-Minimal Descriptions and Computational Structure

Giulio Ruffini
Zenodo (CERN European Organization for Nuclear Research)
Computability, Logic, AI Algorithms
preprint

One Function, Many Programs? Near-Minimal Descriptions and Computational Structure

Giulio Ruffini
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Neuroelectrics Barcelona SLU (Spain) (ES)
Computability, Logic, AI Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon