# When is an upper bound on the longest irreducible program outputting something computable?

Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the same behavior as it.

Given a string $$s$$, we are interested in the longest irreducible program outputting it, and an upper bound on its length. Due to Higman's lemma, the set of irreducible programs outputting $$s$$ is finite, so such a bound must exist.

When is it computable? I can't think of any encoding in which an upper bound would be incomputable, but also not show it's always computable.

If the encoding is unary, only dependent on the length of the string, then we can just look at any program outputting $$s$$ for a bound.

Otherwise, an idea I had was showing that if there's an irreducible program outputting $$s$$ of length $$|p| \geq n$$, then there must be one outputting it of length $$n \leq |p| \leq f(n)$$, where $$f(n)$$ is some computable function, and then from Kőnig's lemma that's enough for an upper bound (which would be very large, but still computable). However, I have no idea if it's true, which $$f$$ to choose, and how to prove it.

Another possible approach might be to construct a set of all irreducible programs which output it, by dovetailing. After some finite time we will find all programs, but we need to somehow tell when we that's the case. Perhaps we can search somehow for a proof that any program that avoids them all can't output the string.

• Just to clarify the question: given a finite alphabet $Σ$, you are asking if there exists a partial computable function $F: Σ^* \dashrightarrow Σ^*$ such that if we call $B_F$ the function taking $s\in Σ^*$ to the greatest length $B_F(s)$ of an element of $L_s := \{p\in Σ^* : F(p){\downarrow} = s\}$ such that no (not-necessarily-consecutive) subword is also in $L_s$, this function $B_F$ is not upper-bounded by a computable function — correct? Commented Dec 16, 2023 at 22:14
• @Gro-Tsen yes, with the added condition that we can translate Turing machines to and from strings $p$, and I prefer natural examples — common programming languages, for example — if those exist. For example, is this boundable if $F$ is a Python interpretor? Commented Dec 16, 2023 at 22:21
• Translating Turing machines “from” $p$ is probably included in the condition that $F$ is computable. But it would be best if you were extremely precise in explaining what you mean by this condition, because what you are asking for seems very much like the sort of things a Friedberg numbering is supposed to make you think twice about: so, is a Friedberg-style numbering a “translation” in your sense? ❧ Also, it would be nice if you gave some background or motivation for the question. Commented Dec 16, 2023 at 22:34
• @JoelDavidHamkins In the context of Higman's lemma, “substring” means a subset of the characters in the program, taken in the same order, but not necessarily consecutive, so even if you require a start-of-program and an end-of-program marker, that does not prevent a substring from being a valid program. (And the argument around Higman's lemma is: assume there were an infinite number of “irreducible” programs $p_i$ producing $s$: order them in some way; then by Higman's lemma we could find $i<j$ such that $p_i$ is a substring of $p_j$, contradicting irreducibility of $p_j$.) Commented Dec 16, 2023 at 23:35
• OK, I can think of another motivation for this question besides code bowling: Kolmogorov complexity of a string is defined as the length of the shortest program that outputs it, so it's natural to wonder about the longest. Now obviously the longest doesn't exist because one can always add stupid stuff to a program, so it's fairly natural to wonder about the longest irreducible program that outputs the string (“anti-Kolmogorov complexity”? “Kolmogorov simplicity”? 😅). And then wonder about its computability in some sense. Commented Dec 17, 2023 at 9:50

I can't answer in the case of Python or any such “natural” programming language, but let me show that whenever $$\#\Sigma \geq 2$$ there is an encoding such that the function you define is non-computable.
To be more precise, here's a possible way of doing it: say $$\Sigma = \{C,P\}$$. A valid program is either a nonempty sequence of $$C$$'s, in which case it encodes the $$e$$-th general recursive function where $$e$$ is the length of the string, or a sequence of $$P$$'s, in which case if $$n$$ is its length, then $$n$$ must be the Gödel encoding of a valid proof in ZFC, and the output of the program is the constant function with value the conclusion of that proof. Anything else is considered invalid (and behaves as the totally undefined function).
Now given a string $$s$$, if $$s$$ is a theorem of ZFC, there will be a “proof mode” program that outputs it, namely a proof of $$s$$. The first proof of $$s$$ is an irreducible program in the sense you defined (since substrings of the program can only code valid “proof mode” programs). There will, of course, be a “compute mode” program which does the same, but no matter: to bound the maximal length of a program which outputs $$s$$ we need to bound the length of the first proof of $$s$$, and this is clearly not possible by a computable function. (If you prefer, use the Busy Beaver instead of this, by demanding that the program be a complete execution trace of whatever string you're trying to output.)