[FOM] Short or very short Gôdel codes, anyone?
hendrik at topoi.pooq.com
Thu Jul 12 07:42:36 EDT 2012
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
> > 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,
More information about the FOM