[FOM] A very short coding

[Richard Heck]

On 07/11/2012 05:32 PM, Frode Bjørdal wrote:
> Here is the coding I have in mind. Let there be m symbols in the
> alphabet, including a suffix variable operating variable forming
> operator ' (so (1) v is a variable, (2) a variable concatenated with '
> is a variable and (3) nothing else is a variable.). Let the language
> be Polish.  ' is assigned 0, and the other symbols in the alphabet are
> assigned the other digits in the base m number system. Concatenation
> is easily defined, and the Godel code of a string of n symbols is the
> number in base m gotten by concatenating the digits in base m
> representing the symbols occurring in the string of n symbols. The
> number value of the code of a string of n symbols in base m is now
> smaller than m raised to n, so this is a very short coding.
>
> This coding has the advantage that we can very directly read off the
> Gödel number of an expression.
>
There's a version of this coding in section 6 of this:
http://frege.brown.edu/heck/philosophy/pdf/notes/FormalBackground.pdf
I find it good for introducing students to the idea of coding. It'd be 
nice to know something about how easy or hard it is, though, to define 
the usual operations on codes using this kind of coding.

Richard