Registered: Mar 2004
Posts: 132

At the Midwest NKS conference this year in Bloomington, Indiana, Matthew Szudzik introduced in his keynote speech a function from mathematical logic that is extremely useful, called the pairing function.

The pairing function lets you take two numbers and create a unique number with them. There is also an inverse function he gave, that takes a number and creates the original two numbers.

He also said that there are other functions and ideas from mathematical logic that are highly relevant to NKS study, but not well known because they were never really used in computer science, which is a field of study that originates from mathematical logic.

These functions are incredibly useful for anyone wanting to set up enumeration schemes, and in general give a single number for every coordinate in an infinite space.

They follow as:

pair[x_, y_] := (x^2 + x + 2x y + 3y + y^2)/2

this number can be transformed back into the original two numbers by:

unpair[z_] := With[{i = Floor[-1/2 + (Sqrt[1 + 8 z])/2]}, {1/2 i (3 + i) - z, -1/2 i (1 + i) + z}]

This can be used to enumerate all state configurations of multiple infinitely growing paramaters. You can think of it as a way of growing towers so that every configuration of tower height is visited and has a unique number for it.

this function is only designed for two parameters but one can imagine a kind folding that pairs many parameters together by successively combining your set of numbers. Such a function can be constructed. One implementation of this is as follows:

Combine[sequence__] := Fold[pair[#2, #1] &, First@{sequence}, Rest@{sequence}]

To uncombine a number into a set of other numbers, the number of parameters must be specified. Here is the code for that:

Uncombine[number_, numParams_] := Reverse[Nest[Flatten[{Most@Flatten@{#}, unpair[Last[Flatten@{#}]]}] &, Last@{number}, numParams - 1]]

Attached is a notebook containing these functions. They are useful when you want a number for every kind of thing x. Enjoy.

Attachment: enumspace-5.nb
This has been downloaded 1113 time(s).

Last edited by Jesse Nochella on 11-08-2005 at 05:21 PM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 20

I suppose it may be obvious, but in concept one can enumerate directed networks in this fashion. Here's a notebook illustrating the concept.

Attachment: enumerating directed networks using the pairing function.nb
This has been downloaded 1097 time(s).

__________________
Seth J. Chandler
Foundation Professor of Law
University of Houston Law Center
Houston, Texas 77204

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

I think it is fair to point out the unpairing function was first shown by Matthew Szudzik in his opening talk at the NKS Midwest conference in Bloomington, around the end of October. Quite useful. Jesse noted above that Matthew showed the pairing function, which is rather better known. Matthew also showed the unpairing function, which isn't as widely known.

Report this post to a moderator | IP: Logged