Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Wolfram Rule 30 Prizes

rule30prize.org

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Wolfram Rule 30 Prizes

#31

Post by abetusk »

For some context, Wolfram published a book of collected papers called "Cellular Automata and Complexity" [1] where he classified Cellular Automata (CA) into four broad categories:

    I. Convergent uniform final state
    II.  Convergent simple pattern final state
    III. "Random"
    IV. "Complexity"
Where "Complexity" essentially means Turing Machine Equivalent [2]. See also [3].

Later, Wolfram self-published "A New Kind of Science" (ANKoS). ANKoS is abysmal and barely readable but, from what I can understand from what little I read of it, Wolfram updated his understanding and instead basically classified CA into two categories, either 'simple' or 'complex', where, again, 'complex' means Turing Machine Equivalent.

If I remember correctly, I think Wolfram even used Rule 30 as a basis for random number generators somewhere (Mathematica?).

Considering the tenor of the problems, maybe Wolfram is still essentially classifying CA into his four initial categories as it looks like he's pushing for the idea that "Rule 30 == 'random'".

My personal take on this is that the idea that there are basically "two" classifications of CA, either 'simple' (non-Turing Machine equivalent) and 'complex' (Turing Machine equivalent) is correct. Though it might be the case where the more 'random' a CA looks, the harder it is to do the reduction to TME, maybe even going so far as having a diverging reduction cost.

Regardless, this is why these questions might be interesting. Is Rule 30 TME? If so, then that answers question 3 (O(n) simulation is essentially saying there's no "shortcut" and you're basically doing full computation). Questions 1 and 2 are, in my opinion, shades of the same TME question, where non-periodic is another way of saying there's no short-circuit computation and calculating the average is getting at the unpredictability (read 'required computability') of the cells.

If Rule 30 isn't TME but still requires O(n) cost to predict, that's also pretty interesting as it requires as much computing power to predict it but isn't as powerful as a Turing Machine. From a broader perspective, this gets at the whole "randomness vs. determinism" idea, as this is a deterministic system that, for many purposes, behaves randomly. This idea is probably old news to this crowd but there's a close link to TME and randomness that is still not completely understood and investigations into CA of this sort are another way to tackle this idea.

[1] https://www.amazon.com/Cellular-Automata-Complexity-Collecte...

[2] https://en.wikipedia.org/wiki/Turing_machine_equivalents

[3] https://www.wolframscience.com/nks/p231--four-classes-of-beh...

Re: Wolfram Rule 30 Prizes

#32

Post by DonHopkins »

wwarner wrote: post #28

An aside: 3D cellular automata https://www.youtube.com/watch?v=_W-n510Pca0

Very beautiful and artistically rendered! Those would make great fireworks and weapons in Minecraft!

From a different engineering perspective, Dave Ackley had some interesting things to say about the difficulties of going from 2D to 3D, which I quoted in an earlier discussion about visual programming:

https://news.ycombinator.com/item?id=18497585

David Ackley, who developed the two-dimensional CA-like "Moveable Feast Machine" architecture for "Robust First Computing", touched on moving from 2D to 3D in his retirement talk:

https://youtu.be/YtzKgTxtVH8?t=3780

"Well 3D is the number one question. And my answer is, depending on what mood I'm in, we need to crawl before we fly."

"Or I say, I need to actually preserve one dimension to build the thing and fix it. Imagine if you had a three-dimensional computer, how you can actually fix something in the middle of it? It's going to be a bit of a challenge."

"So fundamentally, I'm just keeping the third dimension in my back pocket, to do other engineering. I think it would be relatively easy to imaging taking a 2D model like this, and having a finite number of layers of it, sort of a 2.1D model, where there would be a little local communication up and down, and then it was indefinitely scalable in two dimensions."

"And I think that might in fact be quite powerful. Beyond that you think about things like what about wrap-around torus connectivity rooowaaah, non-euclidian dwooraaah, aaah uuh, they say you can do that if you want, but you have to respect indefinite scalability. Our world is 3D, and you can make little tricks to make toruses embedded in a thing, but it has other consequences."

Here's more stuff about the Moveable Feast Machine:

https://news.ycombinator.com/item?id=15560845

https://news.ycombinator.com/item?id=14236973

The most amazing mind blowing demo is Robust-first Computing: Distributed City Generation:

https://www.youtube.com/watch?v=XkSXERxucPc

And a paper about how that works:

https://www.cs.unm.edu/~ackley/papers/paper_tsmall1_11_24.pd...

Plus there's a lot more here:

https://movablefeastmachine.org/

Now he's working on a hardware implementation of indefinitely scalable robust first computing:

https://www.youtube.com/channel/UC1M91QuLZfCzHjBMEKvIc-A

Re: Wolfram Rule 30 Prizes

#33

Post by lamacase »

breck wrote: post #16

Has anyone seen a version of Rule 30 for a 2D array, instead of 1D? I'm doing some searching but can't find one. Somewhat tangential to my angle of attack, but would be helpful to me.

What would this mean? You could have a rule that just implemented rule 30 for one adjacent row or column of the plane, but that would just give you stripes of 1d rule 30. Is there some obvious way of generalizing the 1d rules to 2d that I'm missing? What properties would you expect to be conserved?

Re: Wolfram Rule 30 Prizes

#34

Post by DonHopkins »

breck wrote: post #16

Has anyone seen a version of Rule 30 for a 2D array, instead of 1D? I'm doing some searching but can't find one. Somewhat tangential to my angle of attack, but would be helpful to me.

There are 2D rules that are aesthetically similar to Rule 30 (in how reactive and "fluffy" they are, and how they tend to perpetuate instead of die down), but a 2D and a 3D rule are fundamentally different.

But you can apply simple transformations on rules, like reflecting them (1D and 2D) and rotating them (2D only), or layering them (having a bunch of lower dimension rules running in parallel). Or you can perform a 1D rule along each horizontal/vertical axis (or even diagonal axis) and then combine them somehow (like XOR). But that will typically have a vastly different behavior.

One of my favorite 2D rules that looks kind of like an animated version of Rule 30 is "HGLASS", named that because it looks kind of like the falling sand in an hourglass. If you run it in a torus (edges wrap around), it tends to settle into a circular dependency tree with gaps bubbling up through it like space between cars in a traffic jam.

https://www.fourmilab.ch/cellab/manual/rules.html#HGlass

This is a five-neighbor two-state two-dimensional cellular automaton found at random by Margolus and Toffoli. It organizes a nice sliding flow on a random screen, and it disassembles solid starting patterns in an interesting way.

You can see it here:

https://donhopkins.com/home/CAM6/

1. Click the gray square in the upper right corner.

2. Click "Rules".

3. Select from the Rule dropdown "von Neumann HGlass Down".

4. Draw in the cells.

5. Click in the histogram at to to change the drawing cell value. Click "Tools" to configure the drawing tool.

6. Play around with the other variants of HGLASS (Up/Down/Left/Right, echo, heat) and parallel rules like 4 HGlass Down / All)

Re: Wolfram Rule 30 Prizes

#35

Post by GistNoesis »

lacker wrote: post #11

It is pretty hard in general to prove that calculating things takes at least O(n) time, so I wouldn't expect that one to be solved any time soon. Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone fi…

>any cellular automaton that has something like 3-dimensional rotational symmetry

Kind of cheating : but a differentiable 3d field of real numbers following a local Hamiltonian evolution is a kind of cellular automaton : it has a lot of states 2^32 and local evolution rules are the mathematical ones for differentiable calculus so they encode the rotational symmetry, you can approximate to any levels of desired precision.

Re: Wolfram Rule 30 Prizes

#36

Post by tiborsaas »

aarestad wrote: post #3

What are the implications of positive/negative answers to these questions, and/or what else aside from "because it's there" motivates answering these questions?

From the detailed problem description:

"If one can show that a system is universal, however, then this does have implications that are closer to our rule 30 problem. In particular, if a system is universal, then there’ll be questions (like the halting problem) about its infinite-time behavior that will be undecidable, and which no guaranteed-finite-time computation can answer."

https://writings.stephenwolfram.com/2019/10/announcing-the-r...

Re: Wolfram Rule 30 Prizes

#37

Post by amelius »

aarestad wrote: post #3

What are the implications of positive/negative answers to these questions, and/or what else aside from "because it's there" motivates answering these questions?

These questions made me think of normal numbers [1] and their properties.

[1] https://en.wikipedia.org/wiki/Normal_number

Re: Wolfram Rule 30 Prizes

#38

Post by nswanberg »

lacker wrote: post #11

It is pretty hard in general to prove that calculating things takes at least O(n) time, so I wouldn't expect that one to be solved any time soon. Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone fi…

For what it's worth, Stephen decided that network was a better model for the universe than a cellular automaton, and thought that space might emerge as a property of that network rather than be "defined in", as in a cellular automaton.

https://www.wolframscience.com/nks/p475--space-as-a-network/

(In the preceding section he discussed some constraints that a cellular automaton would put on the universe model, but didn't dismiss the idea for that reason)

Re: Wolfram Rule 30 Prizes

#39

Post by fnrslvr »

singingboyo wrote: post #17
lacker wrote: post #11

It is pretty hard in general to prove that calculating things takes at least O(n) time, so I wouldn't expect that one to be solved any time soon. Personally, I am curious if there is any cellular automaton that has something like 3-dimensional rotational symmetry. If our universe can be described by a cellular automaton, it isn't obvious to me how such a symmetry could arise, but I wouldn't be surprised if someone fi…

> It is pretty hard in general to prove that calculating things takes at least O(n) time It's much simpler depending on the answer to the first question, right? It's been a while since I've touched big-O, but I'm pretty sure that if the center column is periodic (period of P cells), then it follows that you just have to compute the P cells and then index into them, which makes it O(1).

That would be a refutation of the claim that the calculation takes O(n) (or more correctly Omega(n)) time. If the center column turned out to be periodic, then yeah, you're basically on the right track: you would get an algorithm that runs in time polynomial in log(n).

I'm not sure how hard it would be to prove a lower bound on time for this problem, but if a polynomial space lower bound were proven (i.e. computing the nth square of the central column requires a Turing machine with access to Omega(n^a) space for some a > 0), then you'd have a sparse language in P that's not in L, which would be a huge advance for computational complexity theory. So definitely don't expect that anytime soon.

Re: Wolfram Rule 30 Prizes

#40

Post by core-questions »

DonHopkins wrote: post #9

I gave some links to visualizations of CA basins of attraction including Rule 30 in my previous post about "Garden of Eden" configurations: https://news.ycombinator.com/item?id=14468707 There's a thing called a "Garden of Eden" configuration that has no predecessors, which is impossible to get to from any other possible state. For a rule like Life, there are many possible configurations that must have been created by…

Fantastic writeup and well worth re-posting, thanks. Gotta check out DDLab.
Post reply on HN