Talk:Cellular automaton

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Former good article nominee Cellular automaton was a Engineering and technology good articles nominee, but did not meet the good article criteria at the time. There are suggestions below for improving the article. Once these issues have been addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.
          This article is of interest to the following WikiProjects:
WikiProject Computer science (Rated B-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Systems (Rated B-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
Taskforce icon
This article is not associated with a particular field. Fields are listed on the template page.
 
WikiProject Computing (Rated B-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Applied mathematics

Edit war over link[edit]

A cease-fire is now in place for three days, please discuss the link here, as you all should have been doing already. Pursue dispute resolution if needed. Beeblebrox (talk) 19:47, 11 March 2010 (UTC)

The link in dispute was added by someone with a blatantly apparent conflict of interest, apparently in ignorance of wikipedia policies regarding conflict of interest. Its not a link to a cellular automata site, so to me it doesn't seem to add anything to the article nor does it seem notable enough for inclusion. Unless some rationale is provided for its inclusion I say remove the link.

On the other hand, the very first external link in the external links section is indeed link spam, as indicated by the fact that someone keeps adding it at the very very top of the external links list despite the fact that any reasonable person would realize that most wikipedia users couldn't care less about an open source C++ library. The link was identified as link spam and removed on 5 March 2010. If whois is run on the IP address of the contributer of the link, one finds what looks to be yet another blatantly apparent conflict of interest. 76.125.44.38 (talk) 16:13, 14 March 2010 (UTC)

Looking over the external links I see other problems. The Monash University link looks to be of questionable notability, since no description is provided to say why it is notable. The link to CAPOW should be removed unless a suitable description saying why it is notable is provided for wikipedia users (wikipedia is not a link farm). The link to CAPIG should be removed or at least moved to the wikipedia "Pre Image" article. The link to "Random Cellular Automata by ..." should be removed based upon lack of notability and blatantly apparent conflict of interest. For the same reasons the same link should be removed from the "Multi-agent systams" article. 76.125.44.38 (talk) 16:32, 14 March 2010 (UTC)

In general I'm in favor of cutting back link farms. So while I haven't taken the trouble of looking carefully at all the links, the only one I'd argue strongly for keeping is Golly. (The Wolfram looks like it should be informative, but actually isn't, while MCell is also quite popular but platform-restricted.) —David Eppstein (talk) 16:44, 14 March 2010 (UTC)

More importantly, this article needs proper references and clean-up. Shouldn't be too hard for a scientific topic. Blatantly missing is for example: Wiener & Rosenblueth (1946!). Those authors studied spiral waves in an excitable cellular automaton (to model heart tissue) which shows dynamics very similar to those in the chemical BZ (and other excitable) reaction/systems. In this context, I must raise some doubts that Dewdney (sorry, Prof. Dewdney) was the first to do this (unfortunately, I don't have/know the Sci. Am. article). Also what is the meaning of "So far, no naturally occurring chemical cellular automata have been observed"? This probably refers to the idea that snails use bio-automata to pattern their shells. Such processes, however, are much better described by PDE models (such as the Meinhardt-Gierer models). I would suggest that CAs are fine models to reproduce (some of) those patterns but from a biophysical perspective, PDEs are superior ("more realistic") since they are based in fundamental theories (kinetics, stat. mech.) and allow for the measurement of physical quantities such as diffusion coeffs. and rate constants. Also what is this ref. note 10 (and others)? Looks to me less notable than the disputed link, which at least tells its story in a few lines that wikipedia users might appreciate. I will try to do some changes next week once the lock is gone.Agora2010 (talk) 19:25, 14 March 2010 (UTC)

I have started to remove some of the external links. Agora2010 (talk) 01:04, 16 March 2010 (UTC)

This C++ link seems to be rather persistent. I personally feel that a C++ CA library is too specialized for wikipedia as already stated above by someone else. How can one react to this? How do others feel about this link? Agora2010 (talk) 12:24, 17 March 2010 (UTC)

Agreed it's too specific. It looks like a nice free C++ library for macroscopic CA modelling that has been cited in a few papers but that's not enough. It doesn't fit WP:ELYES or WP:ELMAYBE. Can the person suggesting the link explain why they think it matches WP:EL? Ferkel (talk) 10:24, 18 March 2010 (UTC)

I would argue that it make sense to have a link to the CAPOW page, as this is, so far as I know, the only general purpose CA package which is designed to work with continuous-valued CAs. In particular, CAPOW has CA models of the Wave Equation, as well as Reaction-Diffusion. I don't really understand the relevance of the term of "link farm" in this context. CAPOW was developed at SJSU under research grants with student teams over a number of years, and is freeware meant to stimulate futher study. The two papers on the Introductory page [3] explain more about the purpose of continous-valued CAs. Rudyrucker (talk) 03:23, 25 April 2010 (UTC)

Rudy: It is good to see that you take an interest in the quality of Wikipedia. Good show, man!!! William R. Buckley (talk) 03:56, 25 April 2010 (UTC)

Changes to the "History" Section[edit]

First of my apologies for not being logged in when I edited the section as 67.237.114.167. Here are some explanations of my changes:

I removed the Rucker book as it is not a major part of the field's history.

I removed the Wolfram background. If more biographical background information should be given, then for von Neumann, Wiener, or Ulam.

I added a paragraph on Wiener and Rosenblueth, which I consider to be among the founding fathers of CA research.

It would be very interesting to research the links between Wiener and von Neumann. I read on non-wikipedia pages that the two were part of the "Harvard-Navy-IBM Mark I project" and had formed "The Teleological Society". Who knows more about this?

More references are needed to back the Wiener and Ulam statements. —Preceding unsigned comment added by Agora2010 (talkcontribs) 04:09, 15 March 2010 (UTC)

Also the last statement worries me: "Despite much confusion in the press and academia, the book did not argue for a fundamental theory of physics based on cellular automata, and although it did describe a few specific physical models based on cellular automata, it also provided models based on qualitatively different abstract systems." It sounds like some odd justification rather than an objective statement. Agora2010 (talk) 04:15, 15 March 2010 (UTC)

I modified the statement about Wiener-Rosenblueth. It is reasonable to call them among the founding fathers of CA research, but their model is not a CA, only "CA - like", because it is not totally discrete. The medium is continuous in their model. From around 1990 (as far as I can tell), many authors called the Wiener-Rosenblueth model a CA, but see the 1974 article I added in my edit for an earlier statement that it is not. Consulting the original article also makes this clear. I also added a reference to another Wikipedia article about a true CA model of excitable media from 1978, for which it is possible to prove a theorem characterizing those initial conditions for which nontrivial patterns persist. Sph110 (talk) 02:31, 15 June 2013 (UTC)

A Thought[edit]

I'm not apprised of the proper etiquette; please accept this edit as a question. Do the curators of this site read the forum at forum.wolframscience.com? I would think you would not want to add minute variations on cellular automata to this Wikipedia page; however, some developments since the publication of Dr. Wolfram's ANKOS book, that have been posted there, are significant, central ideas (as central as the generalizations you discuss on this page, in terms of hexagonal lattices). Specifically, the cells-with-memory idea. A. M. Nash anna.m.nash@gmail.com —Preceding unsigned comment added by 70.15.168.211 (talk) 16:27, 11 April 2010 (UTC)

CA and fundamental physical reality[edit]

Hi, I am a Ph.D. Candidate in philosophy and cognitive science: it's me who added the section in the first place - I am writing my dissertation on emergent computation and I found that the CA entry was missing something very important; CA have been studied by some among the most brilliant minds of our time and in recent year there is growing interest for their use and application. Unfortunately, a user deleted completely the paragraph (together with useful references and citations) but I couldn't find the reasons behind his actions, so I undo the change and start this discussion to better understand how to convey the proposed content within the existing entry. —Preceding unsigned comment added by 83.103.119.124 (talk) 07:56, 6 September 2010 (UTC)

I agree that this section is relevant, and should be included, but only if you make it neutral and encyclopaedic. For example, "Andrew Ilachinski points out in his monumental monography" contravenes WP:PEACOCK and WP:NPOV. I would vote to keep all except the first paragraph of your section.
Furthermore, I wouldn't consider Konrad Zuse to be the father of the modern PC. I would attribute that, undoubtedly, to John von Neumann -- he invented both parallel processing, and the architecture where data and program are stored in the same place. Zuse did, admittedly, create the first working implementation of an electro-mechanical computer, but the design of the modern computer exclusively belongs to von Neumann.
Regards, Calcyman (talk) 12:30, 6 September 2010 (UTC)
Thanks a lot for your comments. I also agree with both your observations: "monumental monography" is not neutral and I am gonna change it immediately - thanks for the remark. I also aknowledge that "father of modern PC" is somewhat vague and maybe an overstatement: yes, there is von Neumann and yes (of course!) there is Turing. The original meaning I had in mind was something along the lines of: "first to actually build a modern PC", but it went out wrong. Best Regards JT —Preceding unsigned comment added by 83.103.119.124 (talk) 16:01, 6 September 2010 (UTC)

author of the original article[edit]

Seeing as there are so many references to melanie mitchell in the original article, one can only assume melanie mitchell wrote it. —Preceding unsigned comment added by 131.252.222.216 (talk) 02:44, 23 September 2010 (UTC)

And how is this important? Calcyman (talk) 11:57, 24 September 2010 (UTC)
It isn't important who wrote the first version. Yet, for what it's worth, when I first read the article, and largely owing to the specific content and structure, I thought it had been written by either Stephen Wolfram, or somebody associated with him (even if only as a fan). William R. Buckley (talk) 20:38, 25 September 2010 (UTC)

Reversible[edit]

The setting used in the paper by J. Binghama, B. Binghamb is completely different from the setting used in the section about reversibility. They consider only finite systems with a finite lattice (using either periodic boundary conditions or null boundary conditions). The algorithm they give is linear in the size of the lattice of the finite system. In their setting reversibility is decidable in any dimension. I've removed the reference to this paper since it introduces too much confusion. Gthen (talk) 22:14, 22 October 2010 (UTC)

Is Rule 30 "chaotic"?[edit]

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 (Cellular automaton), I believe that the context of the word where it is first used: "... lead to chaotic, seemingly random histories ... " 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? I have also asked this same question on the Rule 30 page. Old_Wombat (talk) 08:56, 10 May 2011 (UTC)

Answered there. —David Eppstein (talk) 16:15, 10 May 2011 (UTC)

Removed paragraph concerning Wolfram's classification[edit]

I recently removed the following paragraph:

However, it has recently been proven that Kolmogorov complexity can formalize Wolfram's classification, characterize these computing systems by their qualitative behavior and extend the scope of the dynamical investigation to the evolution of cellular automata with different initial configurations successfully classifying (and giving answer to previous concerns) all elementary cellular automata into Wolfram's classes. [Hector Zenil, Compression-based investigation of the dynamical properties of cellular automata and other systems journal of Complex Systems 19:1, 2010]

Since there has been some disagreement over the removal, let me explain my reasoning. First, this paper is not really "formalizing Wolfram's classification": it is proposing its own different classification. I've that too, in a different paper (which I also don't think should be added here), DOI:10.1007/978-1-84996-217-9_6; there is a huge literature on this problem, in which neither my paper nor Zenil's paper stand out (in Google scholar, his has 3 citations, mine 5, neither very impressive yet). So I think citing this one and ignoring all the others gives it undue weight. Additionally, by credulously repeating the claims from the paper and not using an unbiased review of the source, we risk repeating the author's hype rather than covering its content neutrally. And finally, I simply do not believe the claims in the removed paragraph. Kolmogorov complexity cannot be used in anything resembling a successful classification system, because to be successful a classification system has to be usable to classify specific rules, and the undecidability of Kolmogorov complexity makes that problematic at best. —David Eppstein (talk) 21:23, 19 May 2011 (UTC)

Approximating Kolmogorov complexity has been largely shown to be of great use for classifying objects, see e.g. the work of Li and Vitanyi based on compression techniques. The procedure in Zenil's paper classifies all Wolfram's elementary cellular automata (ECA) in exactly the same classes proposed by Wolfram himself even if I may agree that at the end the classification turns out to be different because the paper pragmatically addresses the problem of taking into account the evolution of a CA for different initial configurations, something that was overlooked initially in Wolfram's first classification. I agree on not adding more info until more reviews appear. 90.46.37.131 (talk) 23:16, 20 May 2011 (UTC)
It seems the paper in question has been badly summarized by the IP from Spain. It wasn't formalizing anything. The DOI for your paper doesn't work for me (Springer gives an error), can your write the title? Tijfo098 (talk) 22:28, 19 May 2011 (UTC)
Being capable of classifying ECA with an objective measure is in my opinion a formalization of the specific classification of ECA into Wolfram's classes and something worth to eventually mention. 90.46.37.131 (talk) 23:16, 20 May 2011 (UTC)
"Growth and decay in life-like cellular automata", Game of Life Cellular Automata (Andrew Adamatzky, ed.), Springer-Verlag, 2010, pp. 71-98. There's a free version online at arXiv:0911.2890. By the way, I definitely support your addition of the Culik-Yu material here. —David Eppstein (talk) 00:52, 20 May 2011 (UTC)
I don't see the secondary source that you were asking for for any new addition into this section, could you explain why this one is different? is it the number of citations? Thanks 90.46.37.131 (talk) 23:16, 20 May 2011 (UTC)
David, I find interesting your paper. Thanks for the reference. 90.46.37.131 (talk) 23:20, 20 May 2011 (UTC)
I read the paper and as far as I can say it does not support the claims made in the article, it is interesting that one can get a classification that way but people have been doing that sort of thing for ages, it doesn't say anything particular new, and I don't see that it has even been refereed. There is no guarantee the classification will continue on it is some heuristic classification. In my opinion it should not go into the article and I don't see why anyone would want to try and stick it in. Dmcq (talk) 00:37, 21 May 2011 (UTC)
Notice nobody is trying to stick in... nothing else has been inserted to the section in question other than what David Eppstein *allowed* to be inserted (not sure what the criterion was though or why Eppstein thinks he can authorize or not what is inserted). But your claims that a published paper in a journal (Complex Systems 19:1, 2010) is not refereed is outrageous and only shows once more the bad faith of the friends of Eppstein and Kieffer to crush by any means whatever or whoever they may dislike. I cannot even discuss the content with you given that you cannot even see that the paper is obviously refereed (obviously you haven't read anything). You even go further saying that everybody has done the same for ages... A very scientific claim I guess. I think Eppstein, Kieffer and friends are too enamored of beating straw men and engaged in too much incredibly slipshod reasoning. 90.46.37.131 (talk) 01:04, 21 May 2011 (UTC)
I've struck out that bit about refereed, yes of course it would have been. I did not claim it had not been refereed, I made a silly mistake based where I got the paper from. That I agree with Eppstein that the paper does not say anything worthwhile as far as this article is concerned is my own opinion, I am not a friend or enemy or anything of them. The techniques are quite commonly used in lexical analysis, how do you think people use computers to authenticate paintings for instance nowadays? It is even something I've done a bit of myself and am still developing some extra twiddles to analyze a database of over 4000 scottish country dances. Dmcq (talk) 10:26, 21 May 2011 (UTC)
With all the allegation of bad faith I decided to check where your ip was located and got a hub saying amontsouris in Paris. Now Parc Montsouris is actually in Paris and the University of Paris is where I see this Hector Zenil's email points to. So It sounds to me that you are either that person or a close friend to be going to so much trouble to stick in stuff like this. Please read WP:COI? Dmcq (talk) 10:54, 21 May 2011 (UTC)
I see the ip has been blocked for a week and can't answer. Anyway if they can say something about why the publication should be in when they come back that would be far more constructive than what's gone before. Dmcq (talk) 11:31, 21 May 2011 (UTC)
I'm in Paris and any Whois would tell you so (nothing I'm trying to hide as you seem to suggest), yet I don't see how you got to the Parc Montsouris but it is a nice park in the South of Paris as far as I know, not where the university is though. I have already written that the author of this paper gave a talk recently in the university from where I got to know about it and thought it was nice to see that a procedure with no human intervention could perfectly classify all cellular automata into exactly the classes that Wolfram originally suggested, something that you seem to diminish, and that's fine if it does not convince you. Your reasoning about my IP is as sound as, for example, saying that you are Elvis Presley because your IP is from Mississippi. There are 4 million inhabitants in the proper city of Paris and about 11 million in the greater area. I still don't understand, however, why you want me to make me seen as if I were obsessed by the paper in question as if I had been editing this Wikipedia article other than the original two consecutive times I did before (see the history if you want). Had I wanted to pursuit an edit war I would have done so. I understand you are not convinced by the paper (or my summary) and that is just fine, period. I think it is more constructive, however, to write a summary if not of this paper in particular, of the important results of the papers on this subject (Wolfram's classification) rather than deleting the first contribution I do to Wikipedia, contributions which obviously you are now discouraging with such a suffocating attitude. I was unfairly blocked a week by insane allegations of personal attacks, but if I had not come before is because I have better things to do, like continue studying in my university. Should I wanted to continue arguing I would just do so as you can see that my IP is dynamic (not by personal choice) but again, it is not my battle, nor I consider this is my article. So to you to decide what to accept or reject for this article that cries for improvement. 82.123.116.194 (talk) 19:00, 15 June 2011 (UTC) Greg
I had a look and have not found where you said about a talk at a university. I raised the matter of where you were because it has been experience that people who start accusing others of bad faith are the one who are engaged in it. And yes I thought 11 million out of 6 billion i.e. 1 in 600 was very significant odds. You did not answer any points about disagreements with including the bit you put in but simply engaged in personal attacks which indicated to me you had an emotional attachment to the subject. Dmcq (talk) 22:26, 15 June 2011 (UTC)
That is not significant at all for many reasons, e.g. accounting that someone would give a talk and someone else in the same place would be interested about it. But this conversation takes us nowhere. I don't see what you say I left unanswered. I would be happy to answer specific questions but if you don't convince yourselves of the relevance of the results of something that's perfectly fine for me. I have already explained (and I just did again) why I think it was relevant. 82.123.116.194 (talk) 23:25, 15 June 2011 (UTC)
As a sign of good faith and peace flag I would like to propose someone to do a summary of some papers I think would be relevant to mention. There are, for example, attempts using Lyapunov exponents to classify CA, I could look for some specific ones. Also some topological attempts and Israeli and Goldenfeld's work showing that some prediction of coarse-grained structures in Wolfram's class 3 and 4 may be reducible. I also wanted to make a further clarification concerning Zenil's paper, one objection is that apparently the conclusion says that it is proving something. I think it is proving that algorithmic complexity classifies ECA into Wolfram's classes, that doesn't mean that it proves the general problem in general, specially because as you say, the are both undecidable sides: unreachability and eventually the halting problem and on the other hand the uncomputability of algorithmic complexity. I am not, however, an expert on CA, so I leave wording and summarizing the papers to others. The current summary of the section looks fine for me. 82.123.116.194 (talk) 19:39, 15 June 2011 (UTC)
I don't go in for peace flags or anything like that. If you just deal straightforwardly with improving the article that's all anybody could want on Wikipedia. It is important to not claim more than sources say, WP:5P is I think a good guide to the main principles behind Wikipedia. Dmcq (talk) 22:48, 15 June 2011 (UTC)
Notice that my last intervention was on specific contributions to the discussion of the improvement to the section, yet you focus on my shallow opening about the peace flag that wasn't but an indication that I was trying to leave the previous discussion behind. I have nothing more to contribute. 82.123.116.194 (talk) 23:25, 15 June 2011 (UTC)

Fuzzy[edit]

"Fuzzy cellular automata" is a hot topic in research, but there is nothing about it in the article. — Preceding unsigned comment added by 150.214.75.141 (talk) 10:35, 28 May 2012 (UTC)

Page lacks reference to Holland and Holland machines[edit]

It does have genetic algorithms and Mitchell's work, but it completely lacks John Holland's work. 17:43, 27 June 2012 (UTC) — Preceding unsigned comment added by 143.232.210.38 (talk)

Connection between fractals and cellular atomata?[edit]

Is there any connections between fractals and cellular automata? That is, can a cellular automaton (sometimes) be considered to be a fractal? —Kri (talk) 19:32, 20 August 2012 (UTC)

Not a super duper expert on the most technical aspects, but I don't think the usual rules of something like Conway's are scalable in the same way fractals are. —Torchiest talkedits 19:35, 20 August 2012 (UTC)
Some fractals (notably the Sierpinski triangle can be generated as patterns from simple seeds by some cellular automata. That said, the cellular automaton itself is not a fractal. —David Eppstein (talk) 19:54, 20 August 2012 (UTC)
There's a lot of literature about the fractal structure of space-time diagrams of some cellular automata. I recommend this recent paper which includes a survey of many previous works. —Gthen (talk) 11:35, 27 August 2012 (UTC)

Robots and latttices vs. motion of liquids[edit]

Does anyone know anything about the claims in the article about Neumann's self-replicating robots and Ulam's lattices being the inspiration for cellular automata? The books I'm looking through don't mention that aspect of the history. —Torchiest talkedits 15:52, 25 August 2012 (UTC)

I have, since this initial post, found plenty about von Neumann. I still haven't found a clear description of Ulam's supposed lattice work. I am planning on removing that and rewriting it this weekend unless someone objects. —Torchiest talkedits 18:21, 12 October 2012 (UTC)
Never mind, finally found one. —Torchiest talkedits 19:20, 12 October 2012 (UTC)

Article organization[edit]

I feel like this article has too many very small sections. Does anyone have any ideas for merging or reorganizing them? I am thinking one easy move would be to put the Totalistic section at the bottom of the Classifications section. Another possibility would be to combine a handful of other sections into an Applications section. I'm open to any other thoughts on this. —Torchiest talkedits 20:00, 12 October 2012 (UTC)