FOM: Canonical codings
Stephen Fenner
fenner at cse.sc.edu
Tue Sep 4 13:55:47 EDT 2001
Joe,
On Mon, 3 Sep 2001 JoeShipman at aol.com wrote:
> Godelnumber:{eventually-zero infinite sequences of non-negative integers}-->
> {positive integers}
> Godelnumber((x1,x2,x3,...,x_n,0,0,0,0,.....))=(p1^x1)*(p2^x2)*...*(p_n^x_n)
> where p1,p2,... is the sequence of primes 2,3,5,...
>
> ...
>
> OPair:{ordered pairs of non-negative integers}-->non-negative integers
> OPair((x,y))=x + (x+y)(x+y+1)/2
> This counts pairs
> (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0),(0,4),...
>
Because (0,0) = 0, you can get Godelnumber from OPair in a reasonably
cononical way:
(x1,x2,x3,...,xn,0,0,0,0,...) = (x1,(x2,(x3,(...,(xn,0)))))
Actually, this gives you a bijection
(eventually-zero infinite sequences of nonnegative integers) <-->
(nonnegative integers)
provided we make one minor adjustment: define
OPair(x,y) = y + (x+y)(x+y+1)/2
This works for any pairing function where
OPair(x,y) > 0 ==> OPair(x,y) > y
for all nonnegative integers x,y.
To code all finite sequences of nonnegative integers, identify
0 = [] (the empty sequence)
and
[x1,...,xn] = 1 + (n-1,(x1,(x2,...,(x{n-1},xn))))
This seems canonical to me, but maybe I've been programming in Lisp too
long.
BTW - Does anyone know if (eventually-zero infinite sequence of
nonnegative integers) has a name? I've been calling these things
"omega tuples" in my classes.
Steve
More information about the FOM
mailing list