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

  • 1
    $\begingroup$ You said it yourself – the list is not arbitrary. All you need to be able to do is match an input to an index $i$ into the list $\langle s_i,n_i \rangle$. In addition, the inputs are not arbitrary. There are chosen so that this mapping is computable. $\endgroup$ – Yuval Filmus Jan 15 at 6:49

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.

  • $\begingroup$ That's a nice example--thanks. I will have to do more reading on the general claim for any possibe c.e. or computable set of request pairs. I don't find this claim to be obviously implicit or derivable from the the proofs of Kraft's inequality that I have looked at (Calude, Nies, L&V), but I might just not be seeing it. I understand Kraft's inequality as merely a claim about the existence of 1-1 function from prefix-free strings to other strings, without any direct implication about computability, so it wouldn't be surprising if it the proof didn't show how to compute outputs from inputs. $\endgroup$ – Mars Jan 16 at 16:54
  • $\begingroup$ Maybe there are some examples associated with some proofs of the Kraft inequality that convey the point. Or maybe I need to properly study, rather than skim, the proofs of Kraft-Chaitin that are more elaborate (Nies, Calude, D&H) than Chaitin's simple informal proof in his 1987 textbook, which is the K-C proof I felt I understood. $\endgroup$ – Mars Jan 16 at 16:54
  • $\begingroup$ I still have to read Nies' proof of K-C more carefully than I have, but it still looks to me like it's all devoted to giving an effective procedure for choosing input strings, and then just assumes that once "at stage $n\geq 0$ we ... find a[n input] string $w_n$ of length $r_n$" we can just "set $M(w_n)=y_n$" (p. 88), where $M$ is the machine being specified, and $\langle y_n,r_n \rangle$ is $\langle s_i,n_i \rangle$ in our discussion. It still looks like Nies just assumes that such a machine exists--that we can "set $M(w_n)=y_n$". No doubt he has a good reason for that! But I don't. :-) $\endgroup$ – Mars Jan 16 at 17:43

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.