2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please state the theorem! It is not clear what program $B$ is supposed to do from that quote alone. I assume it is that no such ET can exist? If so, see also this question. $\endgroup$ – Raphael Aug 13 '13 at 8:35
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ But I don't know this set of programs becouse the halting problem, I don't know which programs are going to stop. $\endgroup$ – Pedro Aug 13 '13 at 10:02
  • $\begingroup$ @Pedro: That does not matter; halting is not required anywhere! You enumerate all programs (i.e. also such that don't halt for some inputs) and feed all that are long enough (long as in program length) to ET, which is a black box. In the end, the call P(x) may not terminate, but that is okay; we want B to behave exactly like P, after all. $\endgroup$ – Raphael Aug 13 '13 at 10:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But ET must know if the program is going to stop... so in the very beginig has no sense. $\endgroup$ – Pedro Aug 13 '13 at 10:06
  • $\begingroup$ @Pedro Why does it? But if insist, well, we do show that is can not exist! And if you check out the other question I link, yes, the existence of ET does directly contradict the uncomputability of the halting problem. But that is not of import here. We assume that ET exists as defined and perform proof by contradiction. It seems to me that you struggle with this proof technique, not the concrete proof. $\endgroup$ – Raphael Aug 13 '13 at 10:09
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – Raphael Aug 13 '13 at 10:31

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.