Rule 30 for cellular automata | Hacker News Reader

Rule 30 for cellular automata

mathworld.wolfram.com

20 pointsdolftax19 comments

Open articleView on HN

Rule 110 might also be of interest to people as Turing completeness has been proven for it

http://en.wikipedia.org/wiki/Rule_110

and then used to prove css is turning complete

http://eli.fox-epste.in/rule110-full.html

Is there an explanation of how the CSS implements the state transitions?

I've looked through the style sheets and from what I can tell the grid is actually just a bunch of check boxes and are selectors like

  input:not(:checked) +*+ input:not(:checked) +*+ input:not(:checked) +
                    *+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+ input {
                display: none;
            }

the plus sign meaning adjacent to and the * meaning anything so + * + means 2 over + * + *+ meaning 3 etc

It clearly isn't turing complete because it requires the user to input do the loop portion. If you can't loop, you can't be turing complete.

yeah it's basically turing complete if the turning machine is allowed to be hand cranked

Building programs that generate cellular automata is a fun exercise in any programming language, even if it just spits out ASCII art.

I thought it was interesting to read some philosophical thoughts about this and the other rules. Basically, that since such complex, chaotic, or random patterns can be generated from simple rule sets, and since these simple rule sets cannot be reliably divined in reverse from analyzing these complex rulesets, it basically invalidates the Intelligent Design argument. Those arguments are something along the lines of how incomprehensible outputs can only be generated by incomprehensible inputs (like a higher power, etc).

Logically, it does not invalidate intelligent design.

Using your summary "incomprehensible outputs can only be generated by incomprehensible inputs" this sort of thing only proves that an incomprehensible is not a necessary condition.

To truly invalidate intelligent design, you would need to exhaustively show that incomprehensible inputs never yield incomprehensible outputs.

Ninja edit: The sort of reasoning you discuss does strengthen the basis for evolution by natural selection, as it indicates that comprehensible inputs can yield incomprehensible outputs.

This is all in the realm of logic, not observed evidence supporting one view or the other.

Anyone familiar with a site that'll let you generate/view rule 30 (or similar automata) to some high number of rows? Perhaps in a zoomable, Google Maps-style? My google-fu has failed me in this thus far, but it seems like something that ought to be out there.

Interesting. What is the computational cost (space+time) of this rule when used as a random number generator? Is this practical?

Rule 30 is how Mathematica generates random numbers:

And in Mathematica--ever since it was first released--Random[Integer] has generated 0's and 1's using exactly the rule 30 cellular automaton.

The way this works is that every time Random[Integer] is called, another step in the cellular automaton evolution is performed, and the value of the cell in the center is returned. But one difference from the picture two pages ago is that for practical reasons the pattern is not allowed to grow wider and wider forever. Instead, it is wrapped around in a region that is a few hundred cells wide.

-- http://www.wolframscience.com/nksonline/page-317-text

wow, this seems to me to be incredibly reckless, in a mathematics package. it's gotta be much too simple.

You're banking that this incredibly simple rule doesn't generate any trivial correlations that will make it completely inappropriate for a certain case. (whatever it might be, e.g. as an example that it won't be the case that if you get 2^nth values the first and the last will be the same 66% of the time instead of 50% of the time - or whatever. you're saying that there is no property that is totally non-random and breaks some simple case.)

I mean, fine if it passes basic statistical tests I would accept it in a programming library. But in a mathematics package? seems so irresponsible.

If you're going to accuse a professional mathematics company of not knowing math, you could at least spend 5 minutes to read their explanation of the algorithm, and mention why your pseudorandom number generator is more statistically robust.

I didn't accuse them of not knowing math, I said it seems to be reckless and irresponsible. I don't dispute that the method is statistically robust - in fact I said that this would make it fine in an RNG library in some programming language. (i.e. I would have zero qualms using it as my RNG.)

It's just that if there is anyplace where some numerical correlation might accidentally peek through the curtains, it would be in the kinds of things someone does in mathematics software. Here is a bad algorithm http://en.wikipedia.org/wiki/RANDU that was "in use since the 60s'". I'm sure it's fine for certain uses, but, "as a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious."

How surprised would you be if this very simple RNG turned out to produce incorrect results somewhere?

Wolfram published his analysis of CA RNG in 1986.[1]

Since then, his paper has been cited 408 times.[2]

Richard Feynman tried to crack rule 30, but declared he couldn't. That's probably partly why Wolfram describes rule 30 as "probably my all-time favorite scientific discovery."[3]

You said earlier that "[rule 30 has] gotta be much too simple." Many serious mathematicians have felt that way over the past 30 years, but so far nobody has shown how it is a bad RNG. If someone does so at this point, they would make quite a splash in mathematics....

[1] http://www.stephenwolfram.com/publications/academic/random-s...

[2] https://scholar.google.com/scholar?q=%22random+sequence+gene...

[3] http://www.stephenwolfram.com/publications/short-talk-about-...

I'll check back in once they have Rule 34.

It could be the exception that proves the rule:

http://atlas.wolfram.com/01/01/34/01_01_1_34.html

While a single black square yields a boring line, an alternating initial pattern should yield a checkerboard. So any image including a checkered floor should qualify.

Reply on news.ycombinator.com