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.