[FOM] Short or very short Gôdel codes, anyone?

[Hendrik Boom]

On Wed, Jul 11, 2012 at 11:14:30PM +0200, Frode Bjørdal wrote:
> 2012/7/9 <joeshipman at aol.com>
> 
> >  It's easy to have short Godel codings if your arithmetic has
> > exponentiation as well as addition and multiplication,
> >
> 
> What is the role of exponentiation?

It's traditionally used to make pairs in building godel numbers for 
formulae, the same way cons is used for building s-expressions in Lisp.   
A pair (a, b) can be encoded like 3^a * 5^b.

But Cantor pairing could be used instead, which would use multiplication 
instead.

> 
> 
> > but your inequality doesn't work because m^n is the number of strings with
> > exactly n symbols instead of <=n symbols, so some distinct strings would
> > have to have the same Godel code number.
> >
> 
> I do not quite understand. Why cannot m^n, n>0, be the number of strings
> with n or less than n symbols?

m^n isn't defined as "the number of strings ...".  
m^n is defined as exponentiation, and as it happens it *is* thhe number 
of strings with n symbols.

The number of strings with n or fewer symbols is bounded by (m+1)^n, 
though.

-- hendrik