From: ykingma@accessforall.nl (Ype Kingma)
Newsgroups: sci.math
Subject: Re: Smallest Godel number
Date: Wed, 02 Dec 1998 20:13:15 +0200

In article <73i7lj$qkn$1@nnrp1.dejanews.com>, torquemada@my-dejanews.com wrote:

> .....  Hilbert probably turned
> in his grave! I don't think Chaitin himself figured out that you could
> re-encode programs (though I'd like to know who did. Anyone out there know?).
> However he made the practical step of constructing a 17,000 variable
> 'universal' (polynomial) diophantine equation with one free integer
> parameter. The parameter is essentially a Godel-type encoding of your
> program. Determining whether the equation has solutions for any particular n
> is equivalent to the halting problem. It's kinda scary that such an equation
> exists and that you can write it down - though it's almost obvious such a
> thing should exist.
> 
> > Is that the same Chaitin who pioneered register coloring in compilers?
> 
> Yes! (Though it never seems to work as well in practice as I'd like. :-( )

Meanwhile, I sent Chaitin an email with the question on the smallest Godel
number and your first reply. His answer is:


>From: CHAITIN,-a-t-,watson ibm com
>Subject: The smallest Godel number
>
>>Does any of you know whether someone tried to find the
>>smallest Godel number?
>>I realize the smallest Godel number is at least rather large,
>>and I wonder whether current computers are good enough to
>>find/represent it.
>>Hunting for it is probably more technical than mathematical: it will
>>involve comparing huge numbers in different representations.
>
>Well, I have been working for years on a theory (I call it
>algorithmic information theory) whose fundamental concept
>is a complexity measure H(X) that is defined to be the size in
>bits of the smallest program to calculate X.  That is more
>or less equivalent to defining H(X) to be the base-two
>logarithm of the smallest godel number for X.  It turns out
>that the most interesting feature of this concept is that it
>is impossible to ever determine the smallest godel number for
>something (except in a finite number of cases).  My general
>result is that if H(axioms + rules of inference) is the
>complexity of the formal axiomatic system being used, then
>you can't determine the complexity of anything more complicated
>than H(axioms + rules of inference) + c, where c is a constant
>that I can actually determine.  Here I am taking "godel
>numbers for a calculation" to be synonymous with "programs for
>that calculation considered as positive integers".  For more
>information, I suggest you take a look at one of my
>introductory papers, either the one on the Berry paradox
>   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm2.html
>or the one on elegant lisp programs
>   http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html
>Please feel free to post my reply if you wish.
>Rgds,
>GJC

(His email address is not the original one)

Well, that gives me enough to read for the coming holidays.

Have fun,

Ype Kingma

(email at xs4all.nl)