[Zero]

Hi,

I'm about to read Stephen Wolfram's 2002 book A New Kind of Science. Has anyone read it?

[infurl]

I'm about to read Stephen Wolfram's 2002 book A New Kind of Science. Has anyone read it yet?

I bought a copy of the book in hardcover when it was first published but never did find the time to read it. I eventually gave it away to someone who would be able to make use of it. I think the essence of it was that some things can't be predicted, you have to wait for them to happen.

[Zero]

Ok, emergence, chaos, experimentation... sounds good to me
The Wikipedia article gives a few hints about the content.

What I have in mind is a mix of string rewriting system and cellular automaton.

[Zero]

I think the reception section of the Wikipedia article should be read before the book.

[Zero]

Let's make this digital rain thing work.



Unicode 13.0 contains a repertoire of 143,696 graphic characters.

[Zero]

One basic idea could be to formulate rewriting rules that take into account the neighborhood of cells.

Starting from something like
S ::= BBB
B ::= 0
B ::= 1
Instead of this, the left hand side would include topological information, like north/south/east/west or counting information, like how many match "B" in Moore's neighborhood. I don't like to have to choose between options that seem to have no particular pros/cons.
What we know, is simply that if we want a CA that works in every direction the same, then counting should be preferred. On the other hand, the digital rain looks cool, and having it flowing down doesn't hurt much. The possibility to work with N/S/E/W directions would probably add more possibility to "hand-write" initial configurations & rules and understand what we do, while counting the number of matches in the neighborhood is more a chaotic/emergent flavor of it. Both are cool. Both can be kept.

Another thing, in typical 2D CA, you have one layer only. Why? Let's imagine a 2-layers design, with potentially different mechanisms at work! Hey sounds good, why not 1 layer with directional semantics, and another with proximity semantics? (I'm calling "proximity semantics" the count-how-many-in-neighborhood way of doing stuff).

GRRRRRRRRRRRRRRR

[Zero]

Dear reader, please let me emphasize that infurl and ivan.moony, as reasonable adults, did click the "like" button before I post my childish Matrix stuff

[Zero]

The proximity layer seems pretty easy to design, so I'll start with the other one.

Problem is, I'd like to get rid of wildcards in my patterns, to fall back to Thue-like pattern declaration. In this system, you search for substrings to replace, it's not an entire string-match. So something like
B ::= 1
actually really means
*B* ::= <star>1<star>
And I quite like it, because it's simple. Now here is the problem. If you don't have capturing wildcards, how would you declare a rule where some things should come from the north neighbor and some other from the east neighbor? With wildcards it's easy:
↑ foo #1 ← bar #1 ::= got #1
There, if the north neighbor contains "foo baz" and the east neighbor contains "bar baz", then the calculated (central) cell will contain "got baz".

Something with common longest substring could be nice here.

Edit:

Ok, I got 1 solution, maybe not the nicest but it exists. Limit the number of directions to 1 per rule. It sounds more academic/serious.

↑ foo ::= bar

This would declare that if there's "foo" in one cell, then its south-neighbor will receive its content with "foo" replaced by "bar". Ordering of rules matter: for each cell, you start from the top rule and try each rule in order until you find one that fits, and you apply it.

Another idea could be to see each cell as a stack, where rule push strings... It would highly enhance the system, allowing for really more complex systems to be defined.

Edit:

Oh yeah, the directional layer pushes stuff on stacks queues, and the proximity layers shifts stuff!!!  YAAAA I'm crazy today.

Edit:

I'm so terribly angry. Hugely immensely angry.

The directional layer is more or less in a testable/implementable state, let's get to the proximity layer now. The proximity layer is supposed to count the number of matches in the neighborhood to fire a rule. Something like

3 foo ::= bar

that would mean "if there are 3 fooz in the neighborhood, then get the value and replace it with bar". Wait, which value? Same problem as earlier, can't choose between several neighbors.

Edit:

It's even more than that, since in typical 2D CA, you can have rules to create and rules to keep alive.

Breath.

Keeping it alive or creating it is not the problem, it's easy to count what's around. The real thing here is to choose the new value. We do have a possibility to get the value from the other layer, since we talked about queues, but I'd still like to be able to choose values from the neighborhood.

Anything selective could be used, like choosing the longest value in the neighborhood and applying the replacement. But the longest value doesn't seem to be necessarily the most relevant, so it's not a good idea.

Ooops, it's rising again.

Taking it from the other layer is cool, but there's a need to convey data the other way around, else it's useless. Let's look at the other layer again, see if we can get things back.

So what, just pushing it again on the queue? Feels weird. Also, this would mean we don't need the right hand side in the proximity layer rules anymore. Definitely weird. I don't like it.

It would be possible to only push a given value if rule fires. Like,

3 foo ::= bar

if there are 3 fooz, then this cell becomes "bar", and that's it. Simplistic.

Wait, if there are 3 fooz, then take a value from the other layer and replace foo by bar. Nope. Foo can't be both checked around and replaced by, doesn't make sense.

Trance is going on.

I don't feel stacks/queues are a good idea. For now I put it aside, I'll smoke it later. One value.

[LOCKSUIT]

I've read Wolfram's "A New Kind of Science". It's about pattern forming. I might give it another look.

[Zero]

Yeah, you can tell me what you think.

Back to the original feeling, the proximity layer is supposed to bring a more chaotic/emergent-friendly aspect in the design. It has to have an "explosion" capability, and still be tamable.

Maybe getting closer to typical 2D CA 's simplicity would be a good thing.

3 foo ::= bar

What the hell could that mean?

Edit:

The shape of the rule is simply not correct.
- left: when we do it
- right: what do we do

When we do it is already done. What do we do is the incorrect part. What we do is applying a rule. What do we apply it to? well to the one value that is contained in this cell, whether it comes from the other layer or from this one. What rule do we apply? a rule that's defined in the right hand side.

So it would look more like

3 baz => foo ::= bar

Meaning, if we have 3 baz in the neighborhood, then apply a replace-foo-by-bar rule to this cell's value.

Got it.

Not very explosion-like, though. Could be better.

I'm adding a simple "create out of nothing" possibility again, like this:

3 baz => foo

meaning, if 3 baz are around, then create foo in this cell.
Now we have reduced the model to one-layer. We can maybe go back to a 2-layers design.

What would be really cool is having one layer setting up the rules for the other layer.

[ivan.moony]

I'm thinking of tree like structure incorporating string rewriting. This is something I've been applying to CFG grammars a long time ago. This time I want to apply it to general rewriting. Trees give a nice variable and rule scoping pattern where we see only parents and siblings, while allowing us to reuse the same names meaning different things deeper-into-tree definitions.

Note that CFG rules are in fact rewriting rules, written from right to left.

For example, this CFG:

Code

top -> sum
sum -> sum + fact
sum -> fact
fact -> fact * primary
fact -> primary
primary -> [0-9]+

would be represented by the following tree grammar structure:

Code

(
    (
        (
            (
                [0-9]+ -> primary
            ) | (
                fact * primary 
            )
        ) -> fact
    ) | (
        sum + fact
    )
) -> sum

where only primitive operators are `->`, `|`, and round braces. Now just imagine possibility of writing right sides of `->` operator as sequences, introduce some `<variables>`, and we have an entire term rewriting system. For example, if we want to introduce a function, we write the following in the same language:

Code

(twice <x>) -> (<x> + <x>)

Now we can parse things like `twice 2`, translating to `2 + 2`. Moreover, if we write things like `twice bat`, the parser reports an error, indicating a type mismatch. This typing flows from farthest leaves to the very top expression we try to parse.

[Zero]

Are you suggesting we put trees in cells?

[ivan.moony]

Are you suggesting we put trees in cells?

It's yet another way to do rewriting.

[Zero]

   I'm not against, but I don't see how.

[ivan.moony]

  I'm not against, but I don't see how.

I just brought this out of the naphthalene a few hours ago. Coincidentally, rewriting is then mentioned in this thread, so I felt like sharing it. I'm giving it a second thought now, wanting to replace the whole logic behind esperas (v-parser) project.

I'll give it a week or two to be sure I really like it.

The whole idea is about defining basic s-expression based alternative to output (a kind of HTML in my case). Then, the grammar is extended by a user, by functions that transpile to this base output. Because it is a parser under the hood, functions may have any syntax we want. It seems that functions are fully typechecked using only the parser.

so I'd have the following:

Code

</
    </ node1 </ using grammar1 /> />
    ...
    content1
    ...
    </
        </ node1-1 </ using grammar1-1 /> />
        ...
        content1-1
        ...
        </
            ... tree goes on ...
        />
    />
    </
        </ node1-2 </ using grammar1-2 /> />
        ...
        content1-2
        ...
        </
            ... tree goes on ...
        />
    />
    ...
/>

Grammars are cumulative, which means grammars `1-1` and `1-2` are stacked on top of grammar `1`. In other words, grammars are applied cumulatively to all the children nodes. And, since grammars are full term rewriting systems, they are Turing complete, capable of doing any computations needed for e-teoria project.