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.

extremely precisein 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. $\endgroup$shortestprogram that outputs it, so it's natural to wonder about thelongest. 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. $\endgroup$5more comments