[What is simple input? infintely repeating Lyndon words?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

What is simple input? infintely repeating Lyndon words?
(Click here to view the original thread with full colors/images)

Posted by: Andrius Kulikauskas

I'm preparing for the NKS Summer School. I'm studying the (one-dimensional, white/black) cellular automata, especially Rule 110.

The complexity of the output is very impressive, given the simplicity of the rules, and indeed, that such a rule exists within a small sample, only 256 rules in all.

I started to think that the input which is generating the output - the single black square - is perhaps not simple at all, at least not from the algorithms point of view. By analogy, a delta function isn't simple from the point of view of continuous functions. So I asked myself, what would be simple input? and what might that tell us?

It seems to me that simple input would be periodic input, for example, all white squares across: ....W....
Or all black squares.
....B....
Or alternating black and white squares:
....BW....
And other sequences with small period.
....BBW....
....BWW...
and so on.
The study becomes quite interesting because such periodic states can only get sent to states of the same or smaller period.

So I considered the number of such states of a given period. And the states are given by the Lyndon words on two letters (which are also the aperiodic necklaces). See:
http://www.theory.cs.uvic.ca/~cos/i...cklaceInfo.html
http://www.research.att.com/~njas/s...anguage=english

So I started a graph of the states (the Lyndon words) and which gets mapped to which by Rule 110. Here are the most basic rules:
...BWW... => ...BBW... => ...B... => ...W... => ...W...
and
...BW... => ...B...

Actually, these rules determine the Rule 110! and likewise these 5 Lyndon words determine all of the rules.
Because:
...B... can get mapped to only ...B... or ...W... (so that is 2 possibilities and they determine what happens to the local state "bbb")
likewise ...W... can get mapped to only ...B... or ...W... (and that is 2 more possibilities and they determine what happens to the local state "www")
now the checkerboard state ...BW... (by which I mean the infinite series ...BWBWBWBWBW... and so on) can only be mapped to itself (shifted by 0 or 1 square) or to ...B... or to ...W... so that is 4 possibilities and they determine what happens to the local states "wbw" and "bwb"
and the state ...BBW... (by which I mean ...BBWBBWBBWBBW...) includes a fragment "bwb" and that is already determined so there are two squares that we have to worry about (the "bb") and there are 4 possibilities where that can get mapped to ("bb", "bw", "wb", "ww") and so together that determines the local maps for "wbb" and "bww".
and likewise the state ...BWW... will determine the local maps for "wwb" and "bww" and there will be four possibilities.

So that is 2 x 2 x 4 x 4 x 4 = 256 possibilities in all, which is to say, every possible rule. And for each rule we can make a nice graph of the states, which goes to which.

So for example, from "A New Kind of Science", the "all black" algorithm maps the states:
...W... => ...W...
and ...B..., ...BW..., ...BBW..., ...BWW..., all go to => ...B...

The checkerboard algorithm:
...BWW... => ...BBW... => ...B... => ...W... => ...W...
and
...BW... => ...BW...
is very similar to Rule 110 except for what happens to ...BW...

The fractal algorithm:
...B... => ...W... => ...W...
...BW... => ...W...
...BWW... => ...BBW... => ...BBW...

The Rule 30:
...BBW... => ...BWW... => ...B... => ...W... => ...W...
...BW... => ...BW...

(I have neglected to indicate the "shifts" which may or may not be important depending on what we're studying, whether its the local or global matter)

So these graphs might reveal something (Rule 110 is a tree).

But next I am thinking about considering the allegedly simple input (a single black tile - which really though has "infinite" period - and where did it come from? how did it get there?) that perhaps we can think of it as a mixed mode, a loosely coupled mode of the global states I describe above. So for example it might act as a combination:
...W... + ...BWW... + ...BW... + ...BWW... + ...W...
or perhaps simply:
...W... + ...BWW... + ...BW...
and what I imagine is that only some of the interactions are of interest, which are the ones where the states interfere with each other, and so we might "take the derivative" and focus on those.

I am interested if anybody has taken this kind of approach? And any thoughts. Thank you, Andrius, ms@ms.lt

Posted by: Andrius Kulikauskas

I will note that "Lyndon words of length n can be used to construct a basis for the nth homogeneous component of the free Lie algebra". I don't know about this, but Lie algebras are extremely important in mathematics.

Also, Lyndon words are central to my Ph.D. Thesis "Symmetric functions of the eigenvalues of a matrix". The homogeneous symmetric function Hn of the eigenvalues of a matrix (if I remember correctly) is a generating function for all words - and for their factorizations in terms of Lyndon words (which are coded using the matrix edges Aij is i=>j.) Whereas the elementary symmetric functions En are signed products of cycles (the determinant) and the power symmetric functions Pn give walks on the graphs.

Posted by: Michael Schreiber

"it turns out that the lexicographic sequence of Lyndon words of lengths divisible by n gives the lexicographically smallest de Bruijn sequence (Ruskey)."

http://mathworld.wolfram.com/deBruijnSequence.html

A circular sequence of length a^n which includes all sequences of length n_ from an alphabet of length a_ as contiguous subranges is called a deBruijn sequence.

Comprehensive comparisons of cellular automata rules can thus be performed by running these rules over one deBruijn sequence of length a^n instead of testing all a^n initial conditions individually with their own inputs of lengths n. This reduces computation by a factor of n=(1+2*CArangespec*CAsteps).

There are seven related demonstrations:

http://demonstrations.wolfram.com/s...ld.y=0&limit=20

However there is none yet about Lyndon words so I hope you find ways to create some Lyndon demonstrations about CA, necklace or Lie algebraic aspects of simplicity and periodicity.

http://demonstrations.wolfram.com/s...ld.y=0&limit=20

http://demonstrations.wolfram.com/s...lie%20algebraic

Posted by: Andrius Kulikauskas

Micheal, Thank you for the links and also for helping me understand whether this approach has already been taken.

I hope to meet you! Franz Nahrada of Vienna wrote me that you know each other. He is the leader of the Global Villages working group http://groups.yahoo.com/group/globalvillages/ at our Minciu Sodas laboratory http://www.ms.lt

I wrote a Mathematica program to generate the Lyndon words. But I think my coding is a bit clumsy so I will upload it and perhaps I can get help to write it more elegantly. I didn't find any way to iterate through the members of a list with something like a "for each" statement. Is there such a statement? Or how is that done? I will upload my code.

Posted by: Andrius Kulikauskas

I have started practicing with the NKS Explorer.

Also, I have started thinking about a single black square as an input. How can its behavior be composed of simpler states (from simpler inputs)?

I then realized that the rule 110 and every such cellular automata can be thought of as an action on infinite diagonals (at 45 degrees). This is because the local rule:

A1 B1 C1 => ? B2 ?

can be thought of as a function A1 B1 acting on the diagonal. Note that C1 and B2 are on the same diagonal. So the function A1 B1 acts on C1 to yield B2.

In other words, if we think in terms of a sequence of infinite diagonals, then Dn and Dn+1 determine Dn+2. And then Dn+1 and Dn+2 determine Dn+3 and so on.

If the input was an infinite diagonal, such as all white or all black, or one with some kind of period, such as ...WBWBWB... , then we have quite a regular output. Indeed, locally we can think of the automata as a mapping of pairs of states (one square from each diagonal) into functions (acting on the neighbor to the, say, right). There are only four pairs of states:

white over white
white over black
black over white
black over black

and there are only four functions!

keep the same (white is white, black is black)
flip the value (white becomes black, black becomes white)
make it black
make it white

for Rule 110 we have:

W / W => keep the same
W / B => make it black
B / W => keep the same
B / B => flip the value

for Rule 30 we have:

W / W => keep the same
W / B => make it black
B / W => flip the value
B / B => make it white

for the fractal example we have

W / W => keep the same
W / B => keep the same
B / W => flip the value
B / B => flip the value

This applies to, say, the left side of our output. But note that the right side of our output is - generally - unaffected and proceeds separately. In fact it is the inverse of all of the rules. The left and right hand sides of the output are - typically - unrelated. Note that Rule 110 is missing the rule "make it white". I think that what happens here is that the balance of the complexity all ends up on one side. But I am being inprecise and I will pick up on this later.

If we have as input an infinite diagonal (such as all white - which we do, and all black - which we almost do) then the rest proceeds mechanically. Indeed, let us suppose that our input is an infinite diagonal of all white followed by an infinite diagonal of all black. Then by the rules above the next diagonal is "flip the value" (call it j). And B / J = B / B + B / W and next we have J + I. And next we calculate B + W over J + I and so on. And if we don't care how the diagonal are lined up - which perhaps shouldn't really matter with infinite diagonals - then we will get a rather straightforward evolution - and what looks like quite a regular pattern. That is indeed what we get with Rule 110 on the left hand side, if we look at those diagonals.

However! a "single black square" is even more complicated than that! A single black square is, in essence, an infinite diagonal whose bottom half is an infinite black diagonal but whose top half is an infinite white diagonal. So there is a rupture. And far away from this rupture, off to infinity, everything proceeds as before. But close to this rupture there can be interference affects. And these interference effects I think are from the particular alignments of the cycles, the periods, that make up the infinite diagonals we are studying. Because these cycles are being ruptured at particular points. And that is a disturbance, a fissure, an unraveling, and that propagates slowly. And we see that fissure propagating in the pictures. But all of the activity above that fissure is actually predictable as I describe above. I imagine that the easy part to predict is, for any diagonal, what is the recurring pattern. The hard part to predict is, I imagine, for any particular square, which square in the pattern is it? And that has to be perhaps calculated by brute force. And the most difficult think to know - the heart of the complexity - is the propagation of the bare threads at the fissure.

So I am interested to show that indeed the infinite diagonals have a well defined behavior and to show a straightforward calculation, based on the generation and composition of the arising functions, that expresses the pattern or each diagonal. And I also want to show the inherent problem in understanding how the patterns are aligned.

Has anybody taken such an approach?

My basic direction is to reconsider the idea that a single black square is "simple input". I think that I am showing that:
- The truly simple inputs are the infinite periodic "waves", that the automata can be understood as a map on these waves, and that the nature of the automata is given by this map. Indeed the five inputs ...W..., ...B..., ...BW..., ...BBW..., ...BWW... completely determine the nature of each of the 256 cellular automata.
- We can consider the affect of the automata on "disruptive" input with infinite period, such as all white to the left of a certain point. But is that input a possible output? If it is, then it can make sense within a system that yielded it. And that whole system can be understood as the action of pairs of infinite diagonals, Dn and Dn+1 determining Dn+2, and Dn+1, Dn+2 then determining Dn+3 and so on. And that system will be regular onto itself, which I think means that, it is straightforward how the pattern of each diagonal is created. But what may not be key to the system is our coordinate system with regard to which a particular point in the pattern manifests itself. The diagonals don't care because they are running through all the combinations and they are not working in terms of our particular coordinate system.

So a single black square is even more complicated then input with infinite period. Because such an input can also be an output. But a single black square is never the output of a cellular automata! Such a "local" phenomenon is a "lie" or a "misstatement" , "nonsense", "fiction", "imagination" from the point of view of a cellular automata. It means that the automata has been suddenly "turned on" or that the input space is "expanding". And so the complexity that we see is the propagation of this lie.

I appreciate thoughts and advice!

Posted by: Andrius Kulikauskas

I should add that actually for Rule 110 even the infinite diagonal input as I am considering the starting point may perhaps not possible. Can an infinite white diagonal be the input for Rule 110? What would generate it? It does not map to a function "make it white"! and can the other functions (make it black, flip the values, keep the same) combine to yield that? I think the answer is no, I think the four functions are independent. And two white diagonals make a black diagonal. So there is no way that we could have a white diagonal!

So this means that we have the foundations to make it possible to lie.

Also, there is a relation possible here between the ability of a machine to state a lie, and the implications of Godel's theorems.

Posted by: Andrius Kulikauskas

I have put up my presentation:
http://www.worknets.org/wiki.cgi?LawsOfArchitecture
and see also the survey:
http://www.worknets.org/survey/
and here is part of a letter that I wrote to another group:

I find it helpful to realize that the cells in my toe, in my kidney,
in my heart, in my brain, all have the same DNA, even though they end
up so different.

The distinction between the rule and it input - which is the source of
complexity? also came up for me at the Stephen Wolram summer camp.
Both the rule and its input are key for complexity.

I doubted Stephen Wolfram's point in his book "A New Kind of Science"
that a single black square is "simple input". Actually, I pointed out
that in the context of cellular automata, simple input is anything
periodic, such as all black cells, all white cells, alternating
black-white, or black-black-white, or black-white-white, and so on,
which is to say, infinitely repeated Lyndon words. Periodic input
gives periodic output (of the same or smaller period). Whereas "a
single black square" is input of infinite period. (It turns out that I
was reproducing Stephen Wolfram's work from his 1984 paper "Algebraic
Properties of Cellular Automata"). So what is simple depends also on
the point of view, ours or the automaton's.

It seems that the period attractor states that input heads towards -
the kinds of wallpaper that the automata generates - are key to the
behavior of the automata (perhaps there is an analogy with how genes
can be turned on or off). So I considered if it is possible to create
a wallpaper built up from two different wallpapers. (In Christopher
Alexander's and Nikos Salingaros's work, the wallpaper is important
because it is "open space" that allows for "levels of scale".) I got
lucky and actually stumbled upon a "gene splicing" effect which I hope
to investigate further - the building blocks of the input have the
form AB and CD and then one pair gets cut and rearranged to give AC
and BD and that change then propagates through the whole system
yielding the beautiful activity.
http://www.worknets.org/wiki.cgi?LawsOfArchitecture
So that's an example of the point of Stephen Wolfram's methodology -
that by scouring the data, the outputs it is possible to come across
behavior that one wouldn't plan for if they simply focused on their
own models.

Posted by: Michael Schreiber

Thanks for sharing your artistic presention poster and some of your ideas we discussed at the summer school.

Perhaps it would be helpful to compare explicit quotes from the "Collected Papers" and the "New Kind of Science" book?

Furthermore I would be glad to read more about your approach to simple rules in architecture and social networks.

Please consider to make a demonstration of the beautiful patterns you synthesize or maybe to relate them to your dissertation about "Symmetric Functions of the Eigenvalues of a Matrix".

Your dissertation features many creative illustrations so I guess some might be turned into interactive explorations of properties which characterize symmetric matrix functions.

Posted by: Andrius Kulikauskas

Michael, Thank you for being my advisor at the summer school. I very much enjoyed your encouragement.

I lead the Minciu Sodas laboratory for serving and organizing independent thinkers, http://www.ms.lt I enjoyed meeting Stephen Wolfram, a great independent thinker. I was impressed by the leaders of his New Kind of Science team. I would love some day to work for you.

I am glad for his interest in social networking and that he saw my proposal
http://www.worknets.org/wiki.cgi?ANewKindOfCulture

After the summer school, I pursued further my theoretical ideas. I wrote the following proposal
http://www.worknets.org/wiki.cgi?CellularAutomata
see also the Mathematica notebook
http://www.worknets.org/upload/Andr...archproposal.nb
I will post this at forum in a separate thread. I would love to work openly on these theoretical challenges and engage others to advance and apply A New Kind of Science.

Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings