5 ms·
Rule 30 for cellular automata
- gacacplx 11y agoRule 110 might also be of interest to people as Turing completeness has been proven for it http://en.wikipedia.org/wiki/Rule_110 http://en.wikipedia.org/wiki/Rule_110
- cwmma 11y agoand then used to prove css is turning complete http://eli.fox-epste.in/rule110-full.html http://eli.fox-epste.in/rule110-full.html
- srtjstjsj 11y agoIs there an explanation of how the CSS implements the state transitions?
- cwmma 11y agoI'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
- habitue 11y agoIt 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.
- cwmma 11y agoyeah it's basically turing complete if the turning machine is allowed to be hand cranked
- amelius 11y agoInteresting. What is the computational cost (space+time) of this rule when used as a random number generator? Is this practical?
- fjarlq 11y agoRule 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 http://www.wolframscience.com/nksonline/page-317-text
- logicallee 11y agowow, 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.
- srtjstjsj 11y agoIf 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.
- Nihilartikel 11y agoI'll check back in once they have Rule 34.
- TheOtherHobbes 11y agoIt could be the exception that proves the rule: http://atlas.wolfram.com/01/01/34/01_01_1_34.html http://atlas.wolfram.com/01/01/34/01_01_1_34.html
- indrax 11y agoWhile 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.
- _greim_ 11y agoBuilding programs that generate cellular automata is a fun exercise in any programming language, even if it just spits out ASCII art.
- tunesmith 11y agoI 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).
- greggyb 11y agoLogically, 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.
- mikejarema 11y agoAnyone 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.