[FOM] Short or very short Gôdel codes, anyone?
frode.bjordal at ifikk.uio.no
Wed Jul 11 17:14:30 EDT 2012
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?
> 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?
This is OK if one of the symbols is blank and you have the convention that
> initial blanks are ignored, then you can treat blank as 0 in a base-m
> numbering, and two strings with different numbers of blanks in front are
> -- JS
> -----Original Message-----
> From: Frode Bjørdal <frode.bjordal at ifikk.uio.no>
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Sent: Mon, Jul 9, 2012 1:09 pm
> Subject: [FOM] Short or very short Gôdel codes, anyone?
> Has someone used short or very short Gôdel codings to arithmesize
> syntax? If so, who, where and how? A very short Gôdel coding would in my
> idiolect be one where an expression with n symbols, in a system with an
> alphabet of m symbols, would have a Gôdel number smaller than m raised to n.
> Frode Bjørdal
> Professor i filosofi
> IFIKK, Universitetet i Oslowww.hf.uio.no/ifikk/personer/vit/fbjordal/index.html
> FOM mailing listFOM at cs.nyu.eduhttp://www.cs.nyu.edu/mailman/listinfo/fom
> FOM mailing list
> FOM at cs.nyu.edu
Professor i filosofi
IFIKK, Universitetet i Oslowww.hf.uio.no/ifikk/personer/vit/fbjordal/index.html
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM