Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?

Question

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.)

Answer 1

Let's take the example in which $n_i = i + 1$. In this case, we can choose the $i$'th program to be $0^i1$. Here is how the prefix-free Turing machine works. It reads the input, and determines $i$. Now it runs a Turing machine which enumerates the list $\langle s_j,n_j \rangle$ until it reaches $\langle s_i, n_i \rangle$, at which point it outputs $s_i$.

More generally, we choose the programs (i.e., the potential inputs to the prefix-free Turing machine) in such a way that we can effectively convert a program $p_i$ to an index $i$. In other words, contrary to what you write, the programs are not arbitrary, only their lengths are. In general the conversion from program to index might require partial knowledge of the sequence $n_i$.

The actual programs can be constructed greedily. See for example lecture notes of Satyadev Nandakumar, proof of Theorem 3.3.5.

Answer 2

Here's a way to construct a machine that computes $s_i$ from an input $p_i$ that has length $n_i$. It's based on @YuvalFilmus's very helpful answer and the proof of a related theorem by Satyadev Nandakumar, to which Yuval linked. I thought it might be useful to spell out the steps a bit further for anyone else interested in this question--at least, anyone whose insight is impoverished like mine . :-)

As stated in the question, Nies' (Computability and Randomness, theorem 2.2.17, pp. 88f) Machine Existence (Kraft-Chaitin) Theorem assumes that we're given a c.e. set of pairs $\langle s_i, n_i \rangle$, where $s_i$ is to be a result of a computation, and $n_i$ is the length of the input program string that will cause $s_i$ to be computed. (There is an additional important requirement on the $n_i$ that's not relevant to my question.) As I noted in the question, most of Nies' proof consists of showing how a set of input strings $p_i$ can be effectively chosen so that they are prefix-free, but he doesn't spell out explicitly how to use this fact to generate the machine that the theorem claims exists.

When an input $p$ to the machine is received, store it on a tape. Then begin enumerating the pairs $\langle s_i, n_i \rangle$.

As each pair is generated, use the newly generated $n_i$ to generate the next prefix-free input string $p_i$ of that length. (Nies' algorithm generates each prefix-free input string directly from a newly given length $n_i$ along with a set of book-keeping strings generated during the construction of previous strings. There's no reason this procedure can't be interwoven with the generation of the pairs.) Then check whether the original input string $p$ is equal to this newly-generated string $p_i$. If so, output $s_i$ and halt. If not, keep looking: go back to the beginning of this paragraph.

(If the set of pairs $\langle s_i, n_i \rangle$ is infinite, it may be that $p$ is never found among the $p_i$'s, and the process will therefore run forever, in which case the machine only computes a partially computable function.)

In answer to my original question, the above procedure shows that given the assumption that the set of "request" pairs is c.e., a normal finite-state Turing machine is all that's needed. Most of the heavy lifting of constructing the outputs $p_i$ is already present in the original computable enumeration of pairs method, which is available by assumption.

(I suspect that the same construction will work with the prefix-free-string-generation algorithms in other proofs of the Kraft-Chaitin theorem, but I have not checked carefully.)