Neat! That particular bijection's well-know to those who know it, but I hadn't seen the pairing function before. You may also enjoy Chris Barker's Iota, Jot and Zot: http://semarch.linguistics.fas.nyu.edu/barker/Iota/ as well as John Tromp's Binary Lambda Calculus and Binary Combinatory Logic: http://homepages.cwi.nl/~tromp/cl/cl.html My own design, Keraia, is here: http://arxiv.org/abs/cs/0508056 On Fri, Dec 17, 2010 at 9:11 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I have found an interesting bijection between trees (binary trees, not Christmas trees!) and natural numbers, allowing numbers to be displayed as trees, and trees to be associated with numbers. This gives a nice, fun alternative to our positional notation for writing numbers.
The rules are very simple:
* Let the single-point tree, (), be designated the value 0.
* Let the tree (XY) be designated the value ((x+y)²+3x+y+2)/2, where x and y are the values corresponding to the trees X and Y, respectively.
In full parenthetic notation, the first few trees are:
0 () 1 (()()) 2 (()(()())) 3 ((()())()) 4 (()(()(()()))) 5 ((()())(()())) ...
Using the more compact notation of expressing () as * and (XY) as #XY, the trees then become:
0 * 1 #** 2 #*#** 3 ##*** 4 #*#*#** 5 ##**#** ...
And removing the final asterisk results in:
0 (empty string) 1 #* 2 #*#* 3 ##** 4 #*#*#* 5 ##**#* ...
This also serves as an enumeration of Dyck words.
Now, if we replace # with ( and * with ), we have an enumeration of parenthetic statements:
0 (empty string) 1 () 2 ()() 3 (()) 4 ()()() 5 (())() ...
This gives us another enumeration of trees (this time, not restricted to binary trees). For example, the balanced ternary tree:
(()()())(()()())(()()())
can be reverse-engineered into the Dyck word:
##*#*#**##*#*#**##*#*#**
and the binary tree:
##*#*#**##*#*#**##*#*#***
with the full parenthetic expansion:
((()(()(()())))((()(()(()())))((()(()(()())))())))
So, this is a simple bijection between the set of binary trees and the set of all trees, without having to convert to and from integer notation.
We can go further, by allowing more than one type of root node (and slightly altering the 'composition' formula). Letting K = 0, S = 1, and `XY = ((x+y)²+3x+y+4)/2, we have the following:
0 K 1 S 2 `KK 3 `KS 4 `SK 5 `K`KK ...
Ooh, an enumeration of SK-calculus supercombinators. This gets interesting!
(` denotes the application operator)
We can express I as `S`KK, or 9. `S`II then becomes 16389. The number 537231422 corresponds to the irreducible term, ``S`II`S`II.
However, this is not very efficient for unbalanced binary trees. The fixed-point combinator, Y', becomes:
20330403641472985212299390532838786314945647725862859321210046999865821897931
(This is larger than the order of the Monster Group, but smaller than the number of atoms in the Universe.)
So, this is a programming language, where each valid program is an integer, and vice-versa. The rules for an interpreter are as follows, in pseudocode:
(WARNING: May not be suitable for programmers who insist on elegance!)
combinator interpret(int n) {
combinator r;
if (n == 0) { r = K; }
if (n == 1) { r = S; }
if (n > 1) {
int a = 0;
while ((n - (2 + a))*8 + 1 is not a perfect square) // A beautiful test for triangular numbers! { increment a; // Exit when n - (2 + a) is a triangular number. }
b = (sqrt((n - (2 + a))*8 + 1)-1)/2 - a; // This retrieves the side length of a triangular number.
r = apply(interpret(a),interpret(b)) // Recursively call the interpreter on the two sub-terms.
}
return r; // Return the combinator corresponding to the value, n.
}
Merry Christmas!
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com