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 possibly infinite list of strings $ s_i$ , each paired with a desired program length $ n_i$ , there is a prefix-free Turing machine s.t. there is a program $ p_i$ of length $ n_i$ for producing each $ s_i$ , as long as $ \sum_i 2^{-n_i} \leq 1$ . The list of $ \langle s_i, n_i \rangle$ pairs is required to be computable (D&H, Chaitin) or computably enumerable (Nies).

The proofs in the above textbooks work, it seems, by showing how to choose program strings of the desired lengths while preserving prefix-free-dom. The details differ, but that construction is the main part of the proof in each case. The proofs don’t try to explain how to write a machine that can compute $ s_i$ from $ p_i$ (of course).

What I’m puzzled about is why we can assume that an infinite list of results can be computed from an infinite list of *arbitrarily* chosen program strings using a Turing machine that 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’re given a countably infinite list of *arbitrary* results and we match them to *arbitrary* (except for length and not sharing prefixes) inputs, and it’s assumed that there’s no need to argue that a Turing machine can always be constructed to perform each of those calculations.

(My guess is that the fact that the list of pairs is computable or c.e. has something to do with this, but I am not seeing how that implies an answer to my question.)