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

[Frode Bjørdal]

2012/7/12 Hendrik Boom <hendrik at topoi.pooq.com>

> 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.
>
>
The rationale for my question was to probe if it was suggested that
exponentiation was required. The use of sequence numbers to encode
sequences of formulas is of course well known. But these are not necessary,
it seems. Cantor pairing could be used, as you suggest. Perhaps an idea at
least as workable is to separate formulas with the code of an ungrammatical
expression like two adjoined quantifiers?

>
> >
> > > 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.
>
>
I am sorry about the confusion.

The number of strings with n or fewer symbols is bounded by (m+1)^n,
> though.
>
>
More precisely it is (m*(m^n-1))/(m-1).

Frode

> -- hendrik
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>



-- 


Frode Bjørdal
Professor i filosofi
IFIKK, Universitetet i Oslowww.hf.uio.no/ifikk/personer/vit/fbjordal/index.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120713/0b877e02/attachment.html>