Riffs & Rotes & A061396

Tue Jun 26 06:16:07 CEST 2001

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

Marc LeBrun wrote:
> 
> It might be worth noting that these trees themselves can be encoded
> as numbers, thus forming a kind of Godelization of the integers.

Well, I thought that is what I already did,
so I am confused about what you think here.
I am guessing that I forgot to explain how
I first got into looking at these kinds of
correspondences.  I began with an interest
in number theory, and I was always looking
for connections among arithmetic, geometry,
and logic.  Typically, I could always find
a strong correspondence between structures
in two of these domains at a time, but try
as I might, any attempt to bring the third
ring into it would always skunk the circus.

The nearest that I have approached to locating
closely related families of data structures as
arenas for each of these three domains affords
an approach that I can sketch by naming all of
the species of graphs, all of them falling not
far from arboreal, that I happened to discover
turning up over and over again in my inquiries.
These are: (1) planted plane trees, (2) rooted
trees, (3) riffs and rotes, (4) one species of
cacti, the "painted and rooted cacti" (PARC's)
that I have found to be of use in logical work,
as "parse graphs" of propositional expressions.

Though counting ordinary cacti was one of the
fondest problems that I first cut my teeth on,
enumeratively speaking, so many years ago, it
has not been my metier to count everything in
sight for a while, so there might be some new
sequences, of different hues, in these PARC's.
I will append some loose links to these items.
If anybody gets interested I have more formal
definitions of stuff in my dissertation draft.

But one of the reasons for seeking out these correspondences,
aside from their inherent aesthetic interest, is to get them
to bear information from one domain, where it is apparent or
at least a bit easier to see, to another domain, where it is
absent, or obscured, or quite a bit more difficult to locate.

> Let me sketch an example for one of the notations
> I think I saw go by here recently:
> 
> A given number corresponds to an infinite sequence of finite trees,
> all but a finite number of which are empty.  We wish to transcribe
> these into an infinite string of bits, all but a finite number of
> which are 0.
> 
> First we assign each tree (ie each prime) its own infinite subset of bits.
> To the tree rooted at 2 we assign the even bit positions, to the tree rooted
> at 3 we assign every other of the remaining positions (ie the bit positions
> congruent to 1 mod 4), to the tree rooted at 5 we interleave again (ie 3 mod 8)
> and so on, sort of giving each successive prime "half" the remaining positions.
> 
> Next we transcribe the tree rooted at a given prime into these positions.
> If the tree is empty, o, we set all the bits to 0.  If the tree is one, (o),
> we set the least significant bit to a 1 and the rest to 0.
> 
> For the more complex trees we just recurse (I think the exact details of
> the recursion you pick gives you a choice of the different structures
> discussed in this thread, but I'm not sure I understand all that yet!).
> 
> Anyway, the point is that this allows you to map the integers through
> the trees and back into numbers, which opens up many new possibilities.
> 
> We needn't be limited to just taking censi of various populations
> (eg trees of various types).  We can also directly access the
> images of single specific concrete cases numerically.
> 
> For example if f is the mapping (either as we've constructed above,
> or some other way) then there's sequences such as f(n+1) and tables
> of operations such as f(x+y) or f(xy), and for all of these there's
> also their images under the inverse of f.  All of which might be
> entered in the EIS, I imagine.
> 
> And so on ...

I cannot tell here if you are reformulating one of the correspondences
that I discussed or perhaps some other one that passed this way before
my time.  I am a bit biased toward what I think are elegant or natural
correspondences, even if I also want ones that have a use in computing.
Of course, what is elegant or natural may be a highly subjective issue.

Many Regards,

Jon Awbrey

¤~~~~~~~~~¤~~~~~~~~~¤~REFERENCES~¤~~~~~~~~~¤~~~~~~~~~¤

| Notes On The Following Threads:
|
| I am putting every link that I can find that pertains
| to my propositional representation in this collection,
| as I am starting to lose track of what I have already
| written, but there is quite a lot of overlap and some
| other forms of redundancy in the topics covered below,
| so jump around wisely, Grasshopper.  However, just at
| moment, let me direct your attention to the following
| themes and variations among the tangle of topic lines:
|
| 1.  The logically disjunctive representation
|     of a real live dataset under "SIGH's".
|
| 2.  The Peirce's Cook's Turing's representation of
|     a "Space & Time Limited Turing Machine" (STILT)
|     under "Shroud of Turing".
|
| 3.  The RefLog rendition of Sowa's "Top Level Categories" (TLC)
|     whipped up in answer to Jim's query "What Language To Use?"

Extensions of Logical Graphs:

http://www.virtual-earth.de/CG/cg-list/msg03351.html
http://www.virtual-earth.de/CG/cg-list/msg03352.html
http://www.virtual-earth.de/CG/cg-list/msg03353.html
http://www.virtual-earth.de/CG/cg-list/msg03354.html
http://www.virtual-earth.de/CG/cg-list/msg03376.html
http://www.virtual-earth.de/CG/cg-list/msg03379.html
http://www.virtual-earth.de/CG/cg-list/msg03381.html

In Praise of Zeroth-Order Logic:

http://suo.ieee.org/email/msg01406.html
http://suo.ieee.org/email/msg01546.html
http://suo.ieee.org/email/msg01561.html
http://suo.ieee.org/email/msg01670.html
http://suo.ieee.org/email/msg01739.html
http://suo.ieee.org/email/msg01966.html
http://suo.ieee.org/email/msg01985.html
http://suo.ieee.org/email/msg01988.html

Propositional Equation Reasoning Systems (PERS):

http://suo.ieee.org/email/msg04187.html
http://suo.ieee.org/email/msg04305.html
http://suo.ieee.org/email/msg04413.html
http://suo.ieee.org/email/msg04419.html
http://suo.ieee.org/email/msg04422.html
http://suo.ieee.org/email/msg04423.html
http://suo.ieee.org/email/msg04432.html
http://suo.ieee.org/email/msg04454.html
http://suo.ieee.org/email/msg04455.html
http://suo.ieee.org/email/msg04476.html
http://suo.ieee.org/email/msg04510.html
http://suo.ieee.org/email/msg04517.html
http://suo.ieee.org/email/msg04525.html
http://suo.ieee.org/email/msg04533.html
http://suo.ieee.org/email/msg04536.html
http://suo.ieee.org/email/msg04542.html
http://suo.ieee.org/email/msg04546.html

What Language To Use?
Sowa's Top Level Categories,
Sowa's TLC In And Out Of KIF:

http://suo.ieee.org/email/msg01949.html
http://suo.ieee.org/email/msg01956.html
http://suo.ieee.org/email/msg01966.html
http://suo.ieee.org/email/msg02463.html
http://suo.ieee.org/email/msg02466.html
http://suo.ieee.org/ontology/msg00048.html
http://suo.ieee.org/ontology/msg00051.html

Signs, Information, Logic, Inquiry:

http://suo.ieee.org/email/msg02534.html
http://suo.ieee.org/email/msg02554.html
http://suo.ieee.org/email/msg02570.html
http://suo.ieee.org/email/msg02590.html

Sequential Interactions Generating Hypotheses (SIGH's):

http://suo.ieee.org/email/msg02607.html
http://suo.ieee.org/email/msg02608.html
http://suo.ieee.org/email/msg03183.html

Analytic Differential Ontology (ADO):

http://suo.ieee.org/ontology/msg00072.html

Shroud of Turing:

http://suo.ieee.org/email/msg02714.html
http://suo.ieee.org/ontology/msg00308.html
http://www.virtual-earth.de/CG/cg-list/msg03669.html
http://www.virtual-earth.de/CG/cg-list/msg03677.html
http://stderr.org/pipermail/arisbe/2001-January/000167.html

Differential Analytic Turing Automata (DATA):

http://suo.ieee.org/email/msg03004.html
http://suo.ieee.org/email/msg03026.html

Painted Cacti & Propositional Calculus:

http://stderr.org/pipermail/arisbe/2001-January/000150.html

For The Sake Of The Ultimate Reckoning Graph Engine:

http://stderr.org/pipermail/arisbe/2001-January/000168.html

¤~~~~~~~~~¤~~~~~~~~~¤~SECNEREFER~¤~~~~~~~~~¤~~~~~~~~~¤