Registered: Mar 2004
Posts: 132

At the bottom of NKS there lies a lot of combinatorics. I am looking for good ways to create enumeration schemes for various sets of things, and in particular right now symbolic expressions and symbolic transformation rules.

So, as far as I've gotten is that one can easily make all possible expressions of some type with a multiway system. For instance, one can use a rule like "e"->"e[e]" from "e" to get all possible symbolic trees of containing just e; There are also rules that can be added that allow one to generate symbols with multiple arguments. However if one wants to enumerate symbolic transformation rules of some type then one has to go further.

What I want to do eventually is have a setup where there are classes of symbolic transformation rules based on how many distinct symbols they use. So on the left hand side you have some symbolic pattern with at least one copy of each distinct symbol, and on the right hand side you have another pattern with at least one copy of each symbol, in some other tree structure, Like:

z_ [n_ ] [p_ ] [p_ ] -> p [z [z [z [n [p [z ] ] ][n] ] ] [z ] ]

x_ [y_ ] [z_ ] -> z [x [y ] [x [z ] ] ]

That is, on the left hand side they are pattern objects, and on the right they are symbols.

So, it is possible to generate these results with a multiway system of some kind, but these rules do not have an obvious address for each of them. What one needs here is an enumeration scheme, and perhaps even an address for each possible transformation rule that ban be made.

That is, a number for every possible symbolic transformation rule.

There are infinities here to be taken care of, the ones that I see are:

1. There is an infinite number of distinct symbols you can use.
2. There is an infinite number of trees that you can construct with at least one copy of each symbol per amount of symbols that you use.

There are two functions that I think can make this enumeration possible.

1. Nth tuple. Ordinary counting never actually enumerates all possible combinations of elements at every length; for instance the string 010 is never found in binary progression. The set of combinations to be covered with elements e are found by successive Tuples[e,n], where n goes from 1 to infinity. A function that can take a number and map that number directly to the nth tuple that corresponds to that number, of a given set of elements, would be very useful. I have tried to make a function that can do this but have failed multiple times.

2.Nth non-exclusive tuple. I do not know what to call this. Basically, there is a set of elements within tuple-space where at least one copy of each element is in there, and extra copies are further added in all possible ways. I have tried to do this as well and have failed.

At first one may think that there are too many infinities to make an enumeration scheme. I do not claim to know all that entails this task that I have presented so this may well be the case. But as I understand, when you want to enumerate the space all possible somethings, so long as you have a finite amount of infinite sets to enumerate, then a scheme does exist.

My basis for this argument is this: say we want to enumerate all possible rows of black boxes, gray boxes, and white boxes. There are an infinite number of rows of boxes for each color, so if we just set our computer to go through the black boxes first, it would never be able to reach the gray or white ones. But if we told the computer to first go through all of the rows of length one, then length two and so on, The computer would be on its way to enumerating all of them.

In fact, come to think of it even if one had an infinite number of colors that the boxes could be, an enumeration scheme could still be constructed.

Imagine an infinite array whose coordinates correspond to the specification of both box color and box number. If one were asked to scan all of the elements by starting with one row and continuing along until finished, then obviously one would never be able to get to the next row because there in an infinite number of elements to be addressed before then. But to counter this, and in fact eventually cover all rows one can imagine what amounts to a diagonal sweep across the array, that covers every diagonal of the array and properly enumerates every element in it.

What I imagine ideal for defining classes of symbolic transformation rules is this: every possible transformation rule has a number, so something like {245, 23, 9999} could correspond to some symbolic system code. From there, spaces can be defined by putting limits on the number value, and the number of elements in the list, plus they're easy to memorize, it's easy to change the order of them, and there need not be any explicit construction of rules. Although in something like an efficient symbolic system function explicit rules could also be used side by side of numbers in the list of transformations.

And then one would be able to easily investigate the universe of symbolic systems.

Last edited by Jesse Nochella on 10-12-2005 at 01:04 AM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

I can't get excited about abstracted symbolic transformation rules, so must draw on my experience in/basic knowledge of comparable fields. Right now I'm fiddling at the edges of one simple to describe problem and making negligible progress, so I should first focus on some better understood problems.

While the diagonal method can appear to provide a basis for dealing with countable infinities, it helps to be familiar with the difference between countable and uncountable infinities before you start out.

During early research on Tick Tock I was distracted for a while by the problem of exhaustively enumerating simple graphs, trying a method of adding one link at a time to a known set and eliminating dupicates so formed. The only way the indivudual graphs actually got serial numbers was through an autoincrement key in a database to which they were added in the order they were found. Such keys don't tell you anything intrinsic without the database. The number of distinct graphs increases much faster than exponentially with respect to the number of nodes.

Similar problems exist in knot theory, groups and more. I found a similar issue in my 'Trapper' experiment described in the first post I made to this forum where the cyclic states which are found defy useful numbering. A project I am currently trying to find a rationale for to categorise common small unstable configrations in Conway's Life seems to be facing the same problem. In systems where ∃ {A, B, C}: A⇒C ∧ B⇒C ∧ A≠B, mapping to natural numbers does not appear to offer the same benefits as with the likes of CA rule spaces.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Oct 2005
Posts: 1

hi Tony,
I was looking for a simple program to use as a building block the isosceles tetrahedron,and i found your tick tock program .http://www.twistet.com/notch/notches.html You can check my web site, http://www.puzzzlevision.com I am designing ,and crafting 3D mechanical puzzles based on the iso tetrahedron. all i want is to add on my pc the tetrahedron and have all possible shapes so i can then try to make the design.Where can i find this program
thanks, and...
"puzzling makes a better world"

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Michail, I'm replying in a bit more detail by e-mail but should use this opportunity to clear up one point here, even if it is a bit off-topic.

There are currently two projects on my twistet.com site that have nothing more in common than that they involve very different twists on a tetrahedron.

"Tick Tock" was my first serious foray into evolving networks, aka simple graphs, in which the tetrahedron (in the graph theoretic sense) plays a vital role, being conserved under the Tick Tock rule. Tick Tock is a serious original contribution to NKS, but in the 18 months since it was announced here, nobody else has picked it up and run with it and I'm really more interested in reflecting on its potential metaphysical implications than in pushing the model a lot further on my own.

The "Notch" project you mentioned is a very basic exploration of an isoceles tetrahedron which I have since discovered to be well known in model building circles, 24 of which form the space filling rhombic dodecahedron, a shape which has long fascinated me, as per attached note book. The twistet.com domain was registered when we were experimenting with wooden, plaster, paper and 3D wire frame data models.

Attachment: infanto.nb
This has been downloaded 1599 time(s).

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Mar 2004
Posts: 132

In the opening post of this thread I claimed that an enumeration scheme exists for every finite set of infinite sets.

It turns out that this is true. At the Midwest NKS conference this year in Bloomington, Indiana, Matthew Szudzik showed a way to do this for two sets using a function from mathematical logic called the pairing function.

I have given one way of generalizing the pairing function to allow any number of finite sets here. Enjoy.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

Back to Jesse's original question.

One can sometimes use recursive schemes to make an enumeration, following a multiway system. It is general, though not natural.

For instance, for one argument expressions, there are two parts

Head[Argument]

Given a pairing function, Pair[n],
e.g. Pair[n_] := With[{m = Floor[(1+Sqrt[1+8n])/2]},{n-(m(m-1)/2),(m(m+1)/2)-(1+n)}]

expr[0]:=x
expr[1]:=y
expr[n_/;n>=2]:=Module[{a,b},{a,b}=Pair[n-2];expr[a][expr[b]]]

will then get you symbolic expressions in the primitives x and y.
More generally, one could write

expr0[n0_, k_]:=Module[{exprk},
exprk[n_]:=f[n];
exprk[n_/;n>=k]:=Module[{a,b},{a,b}=Pair[n-k];exprk[a][exprk[b]]];
exprk[n0]]

or

expr[n0_, vars_]:=Module[{exprk,k=Length[vars]},
exprk[n_]:=vars[[n+1]];
exprk[n_/;n>=k]:=Module[{a,b},{a,b}=Pair[n-k];exprk[a][exprk[b]]];
exprk[n0]]

which can be used on the right hand side of your symbolic transformations, after the variables have been set from the left hand side.

For instance, with a finite list of variable names (nonempty),

rule[n_,vars_]:=
Module[{vars2,a,b,lhs,rhs,rhs0},
{a,b}=Pair[n];
lhs=expr[a,vars];
vars2=Level[lhs,{-1},Heads->True];
rhs=expr[b,vars2];
lhs=lhs/.x:(Alternatives@@vars):>pattern[x,blank[]]/.{pattern->Pattern,blank->Blank};
(lhs:>rhs0)/.rhs0->rhs]

One might want to use UnsortedUnion so the results do the right thing when the variable list is reordered.

This might not be the best implementation, but it's the first that comes to mind.

Getting a unique rule is more tricky. Hopefully the following is helpful.

The most obvious thing is to use the nth symbol contained when asking for n symbols, and to renormalize so the zeroth expression is the smallest with n symbols, e.g., a[b][c][d]...

Like the above, one can have two enumeration functions.

expr1[a,n] is the a-th expression with symbols coming from the list of the first n variables.
expr2[b,vars,n] is the b-th expression with symbols coming from the list of the first n variables, but definitely containing those from vars.

One would write a recursive function for expr2, like
expr2[m_,vars_,n_]:=Module[{a,b,head,vars2,arg},
{a,b}=Pair[m];
head=expr1[a,n];
vars2=Complement[vars,Cases[head,_Symbol,{0,Infinity}]];
arg=expr2[b,vars2,n];
head[arg]] and so on

Report this post to a moderator | IP: Logged

Registered: Mar 2004
Posts: 132

This is amazing. A more systematic way of browsing symbolic system space is now possible. Soon, that is.

Report this post to a moderator | IP: Logged