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

[joeshipman at aol.com]

It's easy to have short Godel codings if your arithmetic has exponentiation as well as addition and 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. 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 equivalent.

-- 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.



rode Bjørdal
rofessor i filosofi
FIKK, Universitetet i Oslo
ww.hf.uio.no/ifikk/personer/vit/fbjordal/index.html





_______________________________________________
OM mailing list
OM at cs.nyu.edu
ttp://www.cs.nyu.edu/mailman/listinfo/fom

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120709/e8eee549/attachment.html>