Chaitin's elegant programs

Question

I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output.

Here is the proof:

Construct a program $B$ that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$. $B$ runs the elegance tester $\mathrm{ET}$ on each enumerated program $P_k$ in turn until it finds some $P_k$ which $\mathrm{ET}$ claims is elegant. $B$ then runs that $P_k$, thus producing the same output as that $P_k$.

Lemma: B must produce some output.

Proof: There are an infinite number of elegant programs, as noted earlier. So if $\mathrm{ET}$ works as assumed, $B$ must eventually find one of those elegant programs whereupon it will produce that program's output. Now run $B$ with $N$ set to $|B| + 1$ (See note 1). (This is the "threshold size" mentioned in the theorem.) $B$ now will produce the same output as some program $P_k$ which $\mathrm{ET}$ claimed was elegant. But $P_k$ is longer than $B$, so $P_k$ cannot be elegant because $B$, which is shorter, produced the same output. Therefore, $\mathrm{ET}$ was wrong when it claimed $P_k$ was elegant. QED.

My question is: The proof begins with a program $B$ that is a program "that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$" But because of the halting problem such a program is not possible, so the proof starts dead? There is something I'm not understanding here.

Answer 1

The algorithm $B$ is described in a mildly sloppy way. You can look at it as a two-step process:

1. Find suitable $P_k$.
2. Run $P_k$.

Now, step 1 can be done one program at a time since the set of all programs is recursively enumerable and we assume that a recursive (and total) elegance tester $\mathrm{ET}$ exists. Note that we use $\mathrm{ET}$ as an oracle.

So, the algorithm is this:

def B(N,x)
  E = program_enumerator

  do
    P = E.next
    if ( length(P) <= N )
      continue
  while ( !ET(P) )

  return P(x)
end

Why is this a proof? We call the underlying technique proof by contradiction. Here is what happens:

• Assume that a general, total elegance checker $\mathrm{ET}$ exists.
• Under this assumption, construct a (computable!) program $B$ that is equivalent to a program $P$ so that $B$ is smaller than $P$ but $\mathrm{ET}$ says that $P$ is elegant (i.e. smallest).
• Since this is a contradiction, the assumption has to be false; that is, such an elegance checker can not exist.

Answer 2

I assume the description of the algorithm comes from http://www.flownet.com/gat/chaitin.html or a similar text. In particular it explains that both input and code are counted in the size of a program.

One reason why the Halting problem is irrelevant here is that program B does not execute program Pk (in which case indeed we could have programs Pk that do not stop), but only runs ET on the string representation of program Pk.

By definition program ET is a program that always stops after some time. After finishing it returns a program Pk that is elegant. This program Pk therefore produces an output after a finite time so we can safely execute program Pk.

So in a nutshell, neither ET nor B can tell you for any arbitrary program if that programs halts or not.