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.