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

Two programs that compute exactly the same function can look nothing alike inside — different states, different operations, different memory footprints. This paper asks a sharp version of an old question: if you insist both programs be nearly as short as possible, does that force them to be built the same way internally? The surprising answer is: not automatically. Being short constrains how many such programs can exist and how cheaply you can translate one into another, but it says almost nothing about whether their execution traces share any real structure.

The paper carefully separates three different things people often blur together. First, multiplicity: how many near-shortest programs exist for a given function. Second, reconstruction cost: how many extra bits you need to turn one such program into another. Third, structure: whether their actual step-by-step computations — states, transitions, dependency graphs — are related in any meaningful way. Classical information theory (prefix coding, à la Kolmogorov complexity) cleanly bounds the first two for a fixed finite output. Ruffini extends this to whole functions: for total functions (defined on every input), the count of near-minimal programs is bounded by a simple formula in the slack δ, no extra assumptions needed. But turning that count into an actual reconstruction — building one program from another — requires an extra ingredient: a "certification relation," some fixed, trustworthy, listable way of verifying that two programs really do compute the same thing (think: proofs in a fixed formal theory). With that in hand, reconstruction costs about δ plus a logarithmic overhead, and this part also works for partial functions.

None of this touches structure, and that's the paper's real payload. It shows the two properties can come apart in either direction. For minimal linear filters (like digital signal processing recurrences), there really is a uniqueness theorem: any two minimal-state realizations of the same filter are related by an invertible change of coordinates — same structure, just relabeled. Similar rigidity shows up in restricted nonlinear systems (certain recurrent networks) and in optimal bilinear algorithms for 2×2 matrix multiplication. But then the paper gives a clean counterexample: computing x¹⁵ by repeated multiplication has two different optimal five-multiplication chains, and they use different numbers of squaring operations — genuinely different dependency graphs, both optimal, no isomorphism between them. So minimality plus optimality doesn't generally force one shared organization; sometimes it does, sometimes it doesn't, and which case you're in depends on the specific realization class and cost measure, not on program length alone.

The upshot is a research program rather than a closed answer: counting bounds tell you the space of possible descriptions is limited, but classifying what those descriptions actually share operationally requires picking a specific notion of "structure" (which relations get preserved) and proving separate rigidity results for that class — filters, matrix algorithms, physical dynamics, whatever. The paper also flags a hard limit: there's no possible universal, sound, algorithmic test for "these two programs compute the same function," because that would solve the halting problem. So any certification relation you use is necessarily partial, and its choice matters for what the theorems can actually deliver. Practically, this connects to a companion paper (WP0215) asking whether physical systems that produce the same input-output behavior must share the same internal dynamics — same open question, one level up.