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

[jean paul van bendegem]

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
Belgium
http://www.vub.ac.be/CLWF/
 
Managing Editor "Logique et Analyse"
http://www.vub.ac.be/CLWF/L&A

  ----- 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
www.hf.uio.no/ifikk/personer/vit/fbjordal/index.html






------------------------------------------------------------------------------


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