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

Richard Heck rgheck at brown.edu
Mon Jul 9 14:35:00 EDT 2012


On 07/08/2012 10:14 PM, Frode Bjørdal wrote:
> 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.
>
So-called "efficient codings" do get used when working in very weak 
systems of arithmetic, meaning: systems that do not have exponentiation. 
I don't think they go quite as far as you're suggesting, but I've not 
checked the details by any means. See section V.3 in Hajek and Pudlak's 
book.

Richard Heck



More information about the FOM mailing list