The Kraft-Chaitin Theorem (aka KC Theorem in Downey & Hirschfeldt, Machine Existence Theorem in Nies, or I2 in Chaitin's 1987 book) says, in part, that given a likely endless list of strings $ s_i $, each associated with a desired program duration $ n_i $, there is a Turing machine without prefix s.t. there is a program $ p_i $ length $ n_i $ to produce each $ s_i $, as long as $ sum_i 2 ^ {- n_i} leq 1 $. The list of $ langle s_i, n_i rangle $ the pairs must be calculable (D&H, Chaitin) or numerically calculable (Nies).

The evidence in the above manuals works, it seems, by showing how to choose program strings of the desired lengths while preserving the prefix without dom. The details differ, but this construction is the main part of the evidence in each case. The evidence does not try to explain how to write a machine capable of calculating $ s_i $ of $ p_i $ (of course).

What puzzles me is why we can assume that an infinite list of results can be calculated from an infinite list of *arbitrarily* selected program chains using a Turing machine which by definition has a finite number of internal states. Of course, many infinite sequences of results require only finite internal states; consider a machine that simply adds 1 to any input. But in this case, we are given a list infinitely *arbitrary* the results and we match them to *arbitrary* (with the exception of the length and non-sharing of prefixes), and it is assumed that it is not necessary to argue that a Turing machine can always be built to perform each of these calculations.

(I guess the fact that the list of pairs is computable or that has something to do with it, but I don't see how that implies an answer to my question.)