Thanks. It’s only a paragraph but it took me a while to understand Chaitin’s argument, for what it’s worth here’s my take:
Let K(n) = complexity of the integer n. For each integer c, let Sigma(c) be the largest number with complexity c—they call this the “information theory busy beaver function” and indeed Sigma(c) dominates the Turing-style busy beaver function: each computer program of length n will halt before Sigma(n) steps, or not at all. (To see this, note that if a program of length n halts in time t, then we can compute t by running our program, giving K(t) < n and t < Sigma(n).) The problem is that it’s not clear whether an oracle for K(n) allows us to compute Sigma(n) -- Chaitin explains how to compute a more complicated function beta(n).
To define beta(n) you do something like this. Write a computer program P that outputs a sequence (x_1,k_1), (x_2,k_2), … with each K(x) ⇐ k and all such pairs occuring. You can do this without using the K-oracle. Eventually P will output (x,K(x)), and we may use our oracle to tell when. In fact we can use our oracle to tell how many steps it takes before (x,K(x)) appears for every n-digit x, call this function beta(n). Claim: beta(n) is a good substitute for Sigma(n), in the sense that if T > beta(n) then K(T) > n; therefore a computer program of length n halts after beta(n) steps or not at all.
The claim is just the observation that if T > beta(n), then the complexity of T is larger than the complexity of
a maximally complex n-digit number, because we can run P with the additional instruction “stop after T steps” (maybe with a subroutine of length K(T) to generate T) to get this number. The most complex n-digit number has complexity n, and that’s it.
Thanks. It’s only a paragraph but it took me a while to understand Chaitin’s argument, for what it’s worth here’s my take:
Let K(n) = complexity of the integer n. For each integer c, let Sigma(c) be the largest number with complexity c—they call this the “information theory busy beaver function” and indeed Sigma(c) dominates the Turing-style busy beaver function: each computer program of length n will halt before Sigma(n) steps, or not at all. (To see this, note that if a program of length n halts in time t, then we can compute t by running our program, giving K(t) < n and t < Sigma(n).) The problem is that it’s not clear whether an oracle for K(n) allows us to compute Sigma(n) -- Chaitin explains how to compute a more complicated function beta(n).
To define beta(n) you do something like this. Write a computer program P that outputs a sequence (x_1,k_1), (x_2,k_2), … with each K(x) ⇐ k and all such pairs occuring. You can do this without using the K-oracle. Eventually P will output (x,K(x)), and we may use our oracle to tell when. In fact we can use our oracle to tell how many steps it takes before (x,K(x)) appears for every n-digit x, call this function beta(n). Claim: beta(n) is a good substitute for Sigma(n), in the sense that if T > beta(n) then K(T) > n; therefore a computer program of length n halts after beta(n) steps or not at all.
The claim is just the observation that if T > beta(n), then the complexity of T is larger than the complexity of a maximally complex n-digit number, because we can run P with the additional instruction “stop after T steps” (maybe with a subroutine of length K(T) to generate T) to get this number. The most complex n-digit number has complexity n, and that’s it.
The Arslane-Calude argument is over my head.