View source for Talk:Rule 30

{{WikiProject banner shell|class=Start|
{{WikiProject Computer science |importance=}}
}}

== Suggested name change ==

I'd like to add "(cellular automaton)" to the name of this and related articles to avoid conflict with numbered rules in other areas such as rules of procedure. I think this will help with navigation and reduce the need for disambiguation pages.--[[User:RDBury|RDBury]] ([[User talk:RDBury|talk]]) 16:17, 15 May 2009 (UTC)

:Is there a specific article that you are attempting to disambiguate this one from? Because in the absence of a problem I don't see that we need to fix anything. We could conceivably rename it to "Rule 30 (one-dimensional radius-1 cellular automaton with Wolfram naming conventions)" to disambiguate it from all those other Rule 30 cellular automaton articles we might possibly eventually have some day, but I don't see that as helping anyone find the article. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:11, 15 May 2009 (UTC)

::I'm pretty sure only one Rule 30 CA would be considered noteworthy. I was thinking more to avoid collisions with rules from other areas. There are already articles for rule 11, 144, 21, 22, 34, 4, 5, 55, and 6 which have nothing to do with CAs. But I guess the name can always be changed later if becomes a problem.--[[User:RDBury|RDBury]] ([[User talk:RDBury|talk]]) 07:39, 21 May 2009 (UTC)

:::There is a conflict with a possible article on the meme created by 4chan also known as rule 30. Perhaps a disambiguation should be put in place.  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Russell07|Russell07]] ([[User talk:Russell07|talk]] • [[Special:Contributions/Russell07|contribs]]) 10:25, 4 August 2009 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== "Chaotic" behaviour? ==

In [[Chaos theory]], the word "chaotic" is given a very specific meaning, and a distinction is drawn between this meaning and the "common usage" meaning.  Now in this article (Rule 30), I believe that the context of the word where it is first used: "... Rule 30 is a Class III rule, displaying aperiodic, chaotic behaviour... " clearly implies that specific meaning. Now recognizing that I am totally out of my depth here, I ask: does Rule 30 really display "chaotic" behaviour using that word in the Chaos theory context? Can that be "proved", one way or the other? 
[[User:Old wombat|Old_Wombat]] ([[User talk:Old wombat|talk]]) 08:50, 10 May 2011 (UTC)
:Yes, technically it displays sensitive dependence on initial conditions, meaning that if you flip one or a few cells in the middle of a pattern then the region in which the new pattern differs from the old one will in general grow very quickly and without bound. This was one of the properties investigated by Wolfram in his studies of one-dimensional cellular automata. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 16:15, 10 May 2011 (UTC)
::There are many measures used to study the complexity of cellular automata, and difference spreading is one. I think relevant research should be cited when mentioning "chaotic behaviour", since this is indeed an often-misused term. [[User:InverseHypercube|<span style="color:blue; font-size:small;">Inverse</span><span style="color:#6495ED; font-size:small;">Hypercube</span>]] 05:14, 11 May 2011 (UTC)

David, thank you for your reply, but with me being a dumbass I am still confused. The [[Chaos theory]] article cites three criteria; you have addressed only one. 
[[User:Old wombat|Old_Wombat]] ([[User talk:Old wombat|talk]]) 08:21, 11 May 2011 (UTC)
:The chaos theory article also says that those three criteria represent only "a commonly used definition", not a universal requirement. It seems likely to me that the other two criteria hold (for the usual topology in which the fundamental open sets are generated by fixing the states of a finite number of cells and letting the other states vary, and possibly for a restricted subset of the entire state space rather than the entire state space) — for instance, periodic orbits may be found by using initial configurations formed by repeating the same length-k sequence over and over, since such patterns can only evolve to a finite number of other configurations — but I don't know of actual research discussing this issue. As far as I can recall when I've seen "chaos" used in cellular automaton research it refers only to the sensitive dependence on initial conditions part. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 14:43, 11 May 2011 (UTC)
::On further search I found {{doi|10.1016/S0304-3975(95)00022-4}} which proves rigorously that these three conditions are met for [[Rule 90]]. There appears to be some follow-up work which I'll have to track down later; maybe it covers Rule 30. However, the primary investigations of chaos in cellular automata such as this one were by Wolfram in the early 1980s, while the definition you quote is by Devaney in the late 1980s, so insisting on its use in this context is a bit anachronistic. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:36, 11 May 2011 (UTC)
:::One of the later papers, {{doi|10.1016/S0304-3975(98)00345-4}}, explicitly proves that Rule 30 obeys Devaney's three criteria. I'll add a reference to the article. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 19:09, 11 May 2011 (UTC)

== this article seems to similar to Wolfran's page  ==

A quick sight on this article, and the cited http://www.wolframscience.com/nksonline/page-876b-text seems to similar. Is that page text licensed by a Creative Commons or similar copyright scheme?
I am too busy now for a more detailed review, please take a look on this, otherwise Wikepedia may infringe Wolfran's copyright.  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/189.140.234.188|189.140.234.188]] ([[User talk:189.140.234.188|talk]]) 03:16, 13 November 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Wrong (or at least misleading) claim in the main introduction to this article ==

Yesterday I tried to fix an obvious error based on the claim that Sipper and Tomassini's paper proved Rule 30 to behave poorly when used as a pseudo-random number generator when statistically tested. The authors of the cited article admit on page 6 that "The relatively low results obtained by the rule 30 CA may be due to the fact that we considered N random sequences generated in parallel, rather than the single one considered by Wolfram." My change was reverted on the basis that I should cite another paper pointing out the flaw. I don't think any paper is needed if the authors themselves are pointing out they applied their test in certain idiosyncratic way. Clearly many features of rule 30 are not random. For starters, the left side of the rule evolves very regularly and it has even been proved to have a nested periodic on the right boundary too (see "Local nested structure in rule 30" http://thales.math.uqam.ca/~rowland/papers/Local_nested_structure_in_rule_30.pdf). Testing the boundraies for pseudorandomness, for example, would be completely wrong. The claim is clearly misleading with the fact that only some columns have been taken as pseudorandom number generators (the central column in the case of Wolfram and its use in Mathematica). The blog post I mentioned is not from a random comment from a random person, it was written by Daniel Lichtblau (http://mathematica.stackexchange.com/questions/3208/quality-of-random-numbers) from Wolfram's Scientific Information Group who looked at this closely as it would have had a great impact on the performance of one of the PRNG methods available in Mathematica. I think I am making a fair point. If a claim that rule 30 failed an statistical test is kept, I think it cannot go without explaining what methodology was used, and that the methodology used is not compatible with the way in which rule 30 has been used as PRNG. Given that I don't think the Wikipedia page for rule 30 or the cited paper has any particular value for the discussion of rule 30 (their scope was to test an evolutionary program for non-uniform CAs), I found more sensible to delete the citation. Among their own conclusions it was never said they proved anything particular to rule 30 although it could be interesting to mention it later in the article if and only if the methodology is at least briefly explained (test over the full output of the CA evolution). I will try to fix this soon again if nobody else objects. And if someone has the time to add a full nice citation to the paper later in the article that would be nice and I am fine with it.
[[Special:Contributions/130.229.29.179|130.229.29.179]] ([[User talk:130.229.29.179|talk]]) 11:21, 12 August 2013 (UTC)

:: ([http://web.archive.org/web/20160305071904/http://thales.math.uqam.ca/~rowland/papers/Local_nested_structure_in_rule_30.pdf "Local Nested Structure In Rule 30"] archived March 5, 2016) [[User:Jimw338|Jimw338]] ([[User talk:Jimw338|talk]]) 02:04, 6 June 2020 (UTC)

:Wikipedia operates on [[WP:RS|reliable sources]]. What you are doing when you pick out some features of a research study and claim (using your own expertise) that these features make the study a poor match for applications is a form of [[WP:OR|original research]]. If the study is indeed flawed, then the more appropriate way to handle it would be to find reliably published sources pointing out these flaws (you pointed to a web forum but that is not appropriate as a source) and then, rather than removing the information, to include a neutral description of it that considers all relevant points of the view. E.g., saying something to the effect that authors X and Y claim that Z, but author W disagrees, because... —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:30, 13 August 2013 (UTC)

:: When the claim and citation in question was originally introduced, the person who introduced it made a basic call at taking a research result out of important context. What I am doing is actually sticking to Wikipedia's [[WP:OR|original research]] policy, that is, proposing to either put the context in which the result was made and give it less importance given this context, or delete it because it is misleading people to believe something the paper in question is not doing, making readers believe that what the Wikipedia article says one paragraph before the claim in question is that the use of rule 30 as an encryption and PRNG rule system has been proved to be flawed and wrong, which is clearly not what the paper is doing (on top the paper goal is actually away from proving rule 30 PRNG capabilities, and nowhere in the abstract or conclusions says they have done it in any general sense). Taken in context, the paper small result (only one test and performing a different methodology over all rows and not specific columns) on rule's 30 reads very different and I quote (page 6): "The relatively low results obtained by the rule 30 CA may be due to the fact that we considered N random sequences generated in parallel, rather than the single one considered by Wolfram." I am only taking the author's word by word. Now I use my expertise only to explain in this Talk page why the authos said that, and that is also from simply reading their paper too (so not much original research here either...), and that is that they applied their statistical test to all rows of an output of rule 30, and not over the columns that have been used as PRNG (in particular the central). Again, it makes little sense to use rule 30 boundaries as a PRNG or part of a PRNG and it would make little sense if I introduce a claim with a citation to the paper of boundaries saying that also proves rule 30 is a poor PRNG. What you are asking me is to find an article telling a general knowledge fact where the authors of the cited paper decided to apply a measure in a way unrelated to the way in which the previous paragraph in the Wikipedia article is saying rule 30 has been used for as a PRNG. There is a logical inconsistency and lack of vital information in a prominent part of this Wikipedia article and I am trying to fix. It will be very difficult to see someone publishing a paper where they tell all this, it is honestly not worth it, but it is worth it and I am taking the time to try to improve this article by removing misleading information (e.g. people may not even try to apply new measures to rule 30 because the Wikipedia article clearly says that it has already been proved that rule 30 is a poor PRNG!) So I suggest again to delete the claim and citation or move it to a less prominent place with the proper context (if you wish, even quoting the author's words so that I am not told that I am doing original research). Please comment. Thanks. [[Special:Contributions/130.229.29.179|130.229.29.179]] ([[User talk:130.229.29.179|talk]]) 09:58, 13 August 2013 (UTC)
::: In summary:
::: - It is general knowledge that using all the columns at once (or e.g. boundary columns for that matter) is a mistake.
::: - It is not original research, just reading the Sipper and Tomassini paper, and reading the Wolfram paper, to realize they are using different methods.
::: - Sipper and Tomassini express uncertainty in their rule 30 result in the same paper (quoted above).
::: - For reliable sources there is also Wolfram's original paper which describes how to use rule 30 as a RNG or cipher (Wolfram, S. "Statistical Mechanics of Cellular Automata." Rev. Mod. Phys. 55, 601-644, 1983). If Eppstein wants to be precise then the precise statement is that Sipper and Tomassini used rule 30 as a PRNG in a nonstandard way and it failed a chi squared test. That is the claim in their paper, it is not original research. I will make the deletion again in the days to come, others' opinions are welcome. [[Special:Contributions/130.229.29.179|130.229.29.179]] ([[User talk:130.229.29.179|talk]]) 13:28, 13 August 2013 (UTC)
:::: If my long explanations are ignored again, even though I am taking the time to explain and explain the point, my next change will be to cite the same paper as the source of the wrong doing of the paper itself, which is a bit idiotic, but it seems to be what the person reverting my change seems to be asking for. From when on Wikipedia requires to find another reliable source to delete a wrong citation? [[Special:Contributions/80.216.37.78|80.216.37.78]] ([[User talk:80.216.37.78|talk]]) 07:48, 15 August 2013 (UTC)
There is a claim in the published literature, that seems to be widely accepted, that Rule 30 is a bad PRNG. This claim needs to be addressed in the article. By simply removing the claim, you are doing a disservice to our readers. As [[WP:IDIDNTHEARTHAT|I have said repeatedly]] e.g. in my edit summaries, simple removal as you have been doing is the wrong solution. And inserting your own solution that the claim is badly founded because it does something nonstandard is also the wrong solution. You say that the paper sources this claim itself but the jump from the description in the claim to the conclusion that it's the wrong experiment is a violation on your part of [[WP:SYN]]. What you need is to find another published source that either does the experiment better or  refutes the original claim. If it does the whole thing better, it can be substituted, or if it refutes the original claim then we should cite both and explain the disagreement. But either of these two would be better than your pretend-it-never-happened approach, especially as the remaining material in the article implies that it is a good PRNG, something that is not otherwise supported. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 10:54, 15 August 2013 (UTC)
: I think you are doing original research at backing the inclusion of a citation on the basis that you believe that rule 30 is widely accepted to be a bad PRNG (sources??). I am being accused that I am misunderstanding "sourcing and [[WP:SYN]]" but you are advancing a position that has never been claimed in the cited paper even going beyond the paper claim when the authors clearly state concerns about their methodology, hence doing original research yourself against [[WP:SYN]]. That's why I go back to sourcing, because this is the wrong source to back any claim that rule 30 is a bad PRNG (again, if you find someone testing the boundaries, you will not come here and say again that it has been shown that rule 30 is a poor PRNG...) I don't understand what you mean by "You say that the paper sources this claim itself but the jump from the description in the claim to the conclusion that it's the wrong experiment is a violation on your part of [[WP:SYN]]". The article has a clear logical fallacy to go from (quote from the article) "Rule 30 has also been used as a random number generator in Mathematica,[3] and has also been proposed as a possible stream cipher for use in cryptography." followed immediately by "However, Sipper and Tomassini have shown that as a random number generator Rule 30 exhibits poor behavior on a chi squared test..." when methods in both cases are completely different (the standard literature for rule 30 when used as PRNG is to take central columns versus what these authors do that is to take the full output). There is no connection between the 2 (logically linked by "However") sentences whatsoever and this is the true disservice to our readers who are being misled to believe that it has been proven that the way in which rule 30 has been used as PRNG has been shown to behave poorly, perhaps even spoiling any further attempt to really test rule 30 PRNG (for good or bad) capabilities in the standard way or any other way. You need to justify why you want to keep a citation to that part of the article or accept that the sentence needs to be completed by "the authors themselves raised concerns about their methodology (page 6 same paper)". [[Special:Contributions/130.229.29.179|130.229.29.179]] ([[User talk:130.229.29.179|talk]]) 11:48, 15 August 2013 (UTC)
::: I have kept the citation but moved it later in the article in a place that I think is ideal because it is right after the explanation of the way in which Wolfram has suggested rule 30 to be used as PRNG (taking the central column). I also quoted the authors on the methodology so that I am not taken as doing original research. [[Special:Contributions/130.229.29.179|130.229.29.179]] ([[User talk:130.229.29.179|talk]]) 12:01, 15 August 2013 (UTC)
::::The new version looks ok to me. Your clarification of their methodology doesn't add any interpretation, so I don't think it counts as original research. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 23:39, 15 August 2013 (UTC)

== Incorrect description ==

The page claims "... Rule 30 as chaotic based primarily on its visual appearance"

There is no citation, and Wolfram just recently claimed otherwise in an interview with Lex Fridman (t=6919).

He basically explains that he tried many different data analysis methods, and couldn't find a pattern, which is why he assumed it is chaotic.

== Rule set: time goes up or down the diagram? ==
: The following diagram shows the pattern created, with cells colored based on the previous state of their neighborhood. Darker colors represent "1" and lighter colors represent "0". Time increases '''up''' the vertical axis.
Unless I have a hole in my head, surely time increases '''down''' the vertical axis? [[User:Amniarix|◃Λmniarix▹]] ([[User talk:Amniarix|talk]]) 18:01, 7 August 2020 (UTC)

== Mention of the three unsolved rule 30 problems ==

This page should mention the rule 30 problems proposed by Stephen Wolfram: https://www.rule30prize.org/

He's done extensive research on rule 30 and perhaps some of it could be displayed here as well.

At minimum, the three questions are very relevant to rule 30, and some information about them should be displayed

Announcement: https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/

A New Kind of Science is a very valid source for some of this information (again, by Wolfram): <ref>https://www.wolframscience.com/nks/</ref>

[[User:Justingolden21|Justingolden21]] ([[User talk:Justingolden21|talk]]) 22:09, 1 January 2021 (UTC)

{{reflist-talk}}