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

jean paul van bendegem jpvbende at vub.ac.be
Tue Jul 10 03:00:12 EDT 2012

One of the shortest codes I am aware of is to be found in "Computability and Logic" (5th edition) by Boolos, Burgess and Jeffrey, page 188. It groups together symbols by a code consisting of an initial digit smaller than 9 and then adding 9's. Take, e.g., a list of variables: v1, v2, v3, .... These will be coded into,say, 5, 59, 599, ..., so vn requires n signs in the code, satisfying your requirement. The codes of the individual signs are simply joined by concatenation. Jean Paul

Prof.dr. Jean Paul Van Bendegem
Vakgroep Wijsbegeerte en Moraalwetenschappen
Department of Philosophy
Lokaal-Room 5B447
Tel: 02 629 26 61
Centrum voor Logica en Wetenschapsfilosofie
Center for Logic and Philosophy of Science
Vrije Universiteit Brussel
Pleinlaan 2
B-1050 Brussel
Managing Editor "Logique et Analyse"

  ----- Original Message ----- 
  From: Frode Bjørdal 
  To: Foundations of Mathematics 
  Sent: Monday, July 09, 2012 4:14 AM
  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 Oslo


  FOM mailing list
  FOM at cs.nyu.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20120710/4991f06b/attachment.html>

More information about the FOM mailing list