When are two algorithms the same? Towards addressing Hilbert’s 24th problem
Konstantin Doubrovinski · 2025
Read When are two algorithms the same? Towards addressing Hilbert’s 24th problem by Konstantin Doubrovinski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02764.txt.
Introduction
Konstantin Doubrovinski asks when two algorithms should count as the same, in a 2025 paper. The question echoes one Hilbert nearly added to his famous list of open problems, about when two proofs are really the same proof. Since a formal proof is close kin to a computer program, the author poses the question for programs instead, inside recursion theory. He proposes a spare approach built heavily on Kolmogorov complexity, the measure of how short a description of an object can be.
Catalog record
| CREATOR | Konstantin Doubrovinski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-02764
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When are two algorithms the same? Towards addressing Hilbert’s 24th problem Konstantin Doubrovinski Abstract The informal question of when two theorem proofs are “essentially the same” goes back to David Hilbert, who considered adding it (or something roughly equivalent) to his famous list of open problems, but eventually decided to leave it out. Given that the notion of a formal proof is closely related to that of a (computer) program, i.e. a recursive function, it may be useful to ask the same question with regard to programs instead. Here we propose a minimalistic approach to this question within Recursion Theory, building heavily on the use of Kolmogorov Complexity. 1 Background Our notation closely follows vereshchagin2003computable , although it is largely standard. Let us fix Gödel numbering of recursive functions \{\phi_{i}\} . We require that (i) all partial recursive functions are among \{\phi_{i}\} , and (ii) for any partial recursive function of two arguments V(j,x) , there exists a total recursive s , such that V(j,x)=\phi_{s(j)}(x) . The last equality is required for the numbering to be Gödel, see vereshchagin2003computable . We will use the word “program” to informally refer to some index i of some function in our Gödel numbering \{\phi_{i}\} . We can informally refer to Gödel numberings of recursive functions as “programming languages”, and we can refer to isomorphisms of those Gödel numberings (i.e. s defined above) as “interpreters”, whose job is to translate one language into another. Obviously, an interpreter can also map a programming language to itself (defining an automorphism). In what follows, we will only be interested in this situation, i.e. an interpreter will mean total recursive function s such that for our fixed Gödel numbering \{\phi_{i}\} and all i , \phi_{s(i)}\cong\phi_{i} . \cong denotes equality of two programs as functions, i.e. \phi_{i}\cong\phi_{j} iff \phi_{i}(x)=\phi_{j}(x) for all x . We will also need the notion of recursive isomorphism of sets, i.e. recursive bijection of natural numbers mapping one set to another. In what follows, Kolmogorov complexity refers specifically to plain complexity, see e.g. shen2017kolmogorov . In any Gödel numbering, a given function appears infinitely many times (which follows from Kleene’s recursion theorem vereshchagin2003computable ; rogers1987theory ). However, experience shows that not all programs computing the same function are “equally equal”. For example, consider a program that implements Kruskal’s polynomial time algorithm to find a minimum weight spanning tree in a graph with weights assigned to edges (as in Chapter 10 of hopcroft2001introduction ). One can instead implement a brute-force search working in superpolynomial time. These two programs are quite different, even though they compute the same function. Two programs that use exactly the same code to implement brute force search but include different comments, on the other hand, seem to “work the same way”, and are thus “more equal” than the two programs from the previous example. This issue was pointed out and articulated in several previous publications, notably buss2001prospects (page 175, point 3), also blass2009two ; yanofsky2011towards and references therein. Taken together, we wish to come up with a notion of program equivalence that is able to destinguish between our two examples above. Taking programs to be “essentially the same” when they implement the same function is too crude, since a given function may be implemented in “essentially different ways”. Instead, stipulating that programs are “essentially equivalent” when they use the same code is too fine a distinction, since including different comments does not appear to be an essential difference. One may ask whether coming up with new definitions of this kind is of any mathematical value. Our aim is to present evidence that it may be useful, and we certainly hope that it will be. 2 Attempt at definition What makes two programs the same? Assume first that “the same” program is written in two different programming languages. The above discussion suggests that we might declare programs (or pieces of code) the same when some interpreter translating from one programming language to another translates the code of the first program (in one language) into the second program (in another language). Passing to the case when the interpreter translates a language into itself as above, we see that this initial definition does not do the job. Obviously, there always exists an interpreter that maps any \phi_{i} to any \phi_{j} , as long as those compute the same function ( i maps to j , j maps to i , everything else maps to itself). This situation goes to show that any two singleton sets are recursively isomorphic (i.e. one can be mapped to the other by a recursive bijection). In other words, recursive isomorphism is too crude a notion to preserve the structure of singleton objects such as programs or natural numbers. The situation can be overcome by the use of Kolmogorov complexity shen2017kolmogorov ; li2008introduction . Whereas there always exists a bijection mapping one bit string (or natural number) to any other bit string, there may not be a short one. Informally, Kolmogorov complexity may be seen as the “next best thing” to recursive isomorphism since it is approximately recursively invariant in a certain strong sense (invariant up to a constant li2008introduction ; shen2017kolmogorov ). Taken together, we arrive at our next tentative definition: two programs are “essentially the same” when there exists a short interpreter mapping one to another. However, as we will see, this definition is flawed in major ways. First, when demanding the interpreter to be short, it stands to ask compared to what. An obvious answer is perhaps that the interpreter must be short (or, more precisely, Kolmogorov-simple) compared to the sizes of both the input and the output. This makes a good bit of sense at first glance. Indeed, if some short interpreter maps a very complex \phi_{i} to some very complex \phi_{j} , it can not possibly store both programs internally (it’s too short for that). Thus, to “recognize” that \phi_{i} and \phi_{j} are the same, it must be “clever enough” to instead recognize something about their internal structure. An interpreter that eliminates comments from code that it receives as input would fit this definition. However, the definition is still problematic. Notably, it is not transitive, and we must require transitivity if we are aiming to define an equivalence. One could overcome this by forming transitive closure of our current version of the relation. Specifically, we can declare two programs as “essentially equal” if there is a sequence of interpreters mapping one to another, each of complexity less than either of those programs. More formally, \phi_{i} is “essentially the same” as \phi_{j} , provided there is a sequence of interpreters s_{1},...,s_{n} , such that s_{n}(...s_{1}(i)...)=j , and K(s_{m})<K(i),K(j) for all m\in[1,...,n] . This definition is mostly the same as the final one proposed below, but it has a shortcoming. Suppose our programming language allows for the use of subroutines. Suppose \phi_{i} and \phi_{j} compute the same function but are “not the same”, as in the above example with Kruskal’s algorithm. Suppose we come up with programs \Phi and \Psi , both much more complex than \phi_{i} and \phi_{j} . Suppose \Phi and \Psi are exactly the same, except that \Phi calls subroutine \phi_{i} , whereas \Psi calls