Talk:Cellular automaton/Archive 1

Archive 1

The point ...

The point was made by an anon that "There are no theoretical reasons for cellular automaton to be completely self-developing." - what is this property "self developing"? Dysprosia 22:57, 6 Mar 2004 (UTC)

Not entirely sure; I haven't heard of that before. Maybe something along the lines of how, for example, the Game of Life can give rise to collections of cells that give birth to other cells? That's a kind of development, but there are no CAs that exhibit the kind of constantly evolving progress/development as shown by human society.

Maybe anon can expand on the idea for us... Chopchopwhitey 23:49, 6 Mar 2004 (UTC)

I made this point, sorry I forgot to login. The point is that cellular automaton like Conway's Game of Life can implement Turing machine and therefore everything what can be expressed algorithmically, but it's not proved that such complicated structures like Turing machine can emerge in cellular automaton by development, for example by putting some pattern to develop and using some canons as input of different letters or symbols, and getting output somewhere. I mean that what is not proved is that Turing machine etc can be created in cellular automaton by such or similar interaction, a symbolic interaction similar to that in chatbots. A machine where anything can emerge by such interaction, not by programming the system in in a way or another, is completely self-developing. IMHO, don't know it's written anywhere, but it seems obvious. Cellular automaton is wonderful, but also must be considered the ways it might be restricted. tkorrovi

---

I have a question about this statement: "In other words, no pattern exists which will, in one step, become a Garden of Eden pattern." It seems to me that the inserted "in one step" can be removed without losing anything. If there exists a pattern that turns into the "Garden of Eden" pattern in n steps, there must be one that does it in n-1 steps ... induction ... that does it in 1 step.

I suggest changing the sentence to "In other words, no pattern exists which will develop into a Gardon of Eden pattern." — David Remahl 13:34, 18 Jul 2004 (UTC)

This sounds right. I remember reading before (however, a long time ago) that Garden of Eden patterns imply that cellular automata then, using a functional interpretation, are not surjective. Dysprosia 13:56, 18 Jul 2004 (UTC)

I went ahead and changed it. If someone has a problem with this minor point we can always revert. David Remahl 16:31, 18 Jul 2004 (UTC)

positional variations and local connectivity variations

all the variations in the game of life family considers the _number_ of neighboring cells. Where can one read about 2d CA that considers the position of neighbors, besides number? Also, there is zero info on life with different grids. (i.e. triangular, hexagonal, or any tilings/network) (besides Stephen Wolfram's book) Thanks. Xah Lee 00:47, 2005 Apr 5 (UTC)

I've added a link in the References section to different kinds of neighbourhoods. In general, CAs maintain directional invariance (up to the symmetry of the underlying grid) and thus do not consider the positions of their neighbours. But there is no reason why you could not make an orientation-specific CA. Ferkel 11:25, 23 Jun 2005 (UTC)

Thanks. I'll check the link out. By positional variation i mean a variations i mean taking neighbor positions/placement into account. Most CA such as game of life only count the *number* of neighbors, but disregard any placement. Xah Lee 05:59, 2005 Jun 25 (UTC)

the link added isn't worthy. It doesn't have any thing significant to say. All it does is indicating what are the possible grids and definition of neighborhood. It shouldn't be part of encyclopedia, in contrast to most other links there. Xah Lee 06:06, 2005 Jun 25 (UTC)

Mathematical formalization

I agree that my post was "badly written and unsourced" but the current state of the page is not good eather. I have sent a link to the page to the Usenet group on Google [1] to get some feedback, now they can not see the page... (there may be a better way but I am a novice to Wikipedia)

If you have any better "concrete definitions of CA" than please post your suggestions, I used the next definition (approximately) from CA-FAQ [2] (be careful there is an annoying Java fire).

[3]: Wicked demo. Fastest animation download I've ever seen, and this is dialup. Yah! 216.234.170.67 01:28, 2 August 2006 (UTC)

• "Information dynamics of Cellular Automata" by Hidenosuke Nishio

• "Enumeration of preimages in Cellular Automata" by Erica Jen

My intention is to continue with the article on computing preimages but I need a clear definition to start with.

As you can see I used the neighborhood size k and the output cell shift as such a definition is more useful when implementing software, and may be useful to describe hexagonal lattices too.

P.S.: I just moved the page to my personal sandbox User:Iztok.jeras/Sandbox I would appreciate comments and edits. --Iztok.jeras 12:40, 18 July 2005 (UTC)

I have been to the library today looking fore some definitions, with not much sucess. Hire are the three sources I was looking for and some comments:

• Tommaso Toffoli and Norman Margolus, Cellular automata machines

Those two are known to be experts in reversible CA, thought in these book CA especially constructed to be reversible (my next step is to write an article about the computation of the CA preimages (past)). The only think that looked like a formalism was the local transition function $c_{i}^{t+1}=f(\dots )$. And the time index was always superscribed which I mostly changed in my formalization too.

• Stephen Wolfram, Algebraic Properties of Cellular Automata (1984) [4]

This formalization uses polinoms and is specialized for linear cellular automata, not too useful for us. But I just find out there are a lot of CA articles from Wolfram online.

• Stephen Wolfram, Universality and Complexity in Cellular Automata (1984) [5]

Looks better but it does not go far.

• Howard Gutowitz, editor. Cellular Automata: Theory and Experiment, 1991. Published as Physica D45 (1990) Nos. 1-3, and as MIT press book.

It is a collection of articles some of them useful especially those from Erica Jen. The formalization is similar to mine, but hire comes the main problem with CA, there are no naming conventions like for automata, like what are uppercase and lowercase letters used for (Greek letters, and and beginning of the alphabet) so what letters should I choose (I can not look to all articles and find the most common denominations because the subject is not stable yet)

There was another idea I found in a Wolfram article, is not only extending the number of dimensions but to extend the depth in the past that is used to calculate the future (in some reversible CA not only the present but the past too is used to calculate the future)

--Iztok.jeras 21:15, 20 July 2005 (UTC)

Wikibook on Cellular Automata

I inviting all cellar automata fans to visit wikibooks:Cellular Automata. It aims to be a graduate to postgraduate level schoolbook (a lot of definitions formalization and proofs) but there is space for less formal information in some chapters.

Now two pages are 'finished':

• wikibooks:Cellular_Automata/Mathematical_Model formal mathematical model for 1D CA with some generalizations
• wikibooks:Cellular_Automata/Preimages how to compute the past values (for now only their number, the listing of them will come soon)

I would like some comments on:

• how good are they written, especially which parts are too hard to understand so I can improve them
• the table of contents is not finished yet, what should I add

--IzI 17:05, 17 August 2005 (UTC)

Definition of Cellular Automata/Cellular Automaton

There is a misconception regarding these two spellings.

Cellular Automata is not plural for Cellular Automaton.

The pattern of states within some region of cell space is termed a "configuration" with the term cellular automaton referring to some configuration which fulfills some consistent function. For instance, the Real-Time Crossing Organ of von Neumann cellular automata is a configuration that performs the task of crossing signals. Hence, the RTCO is a cellular automaton that functions to facilitate the crossing of signals within von Neumann cellular automata.

The system upon which a configuration may be constructed and operated is a cellular automata. The glider and glider gun are both cellular automatons that operate upon the system of cellular automata known as the Game-of-Life, as specified by John Horton Conway.

The text of this wikipage ought be corrected to reflect this usage of language, which is standard within the research community.

William R. Buckley 06:57, 14 October 2005 (UTC)

No offense, but WTF are you talking about? Automata has never been a singular word in Greek, Latin, or English. I have never heard anyone else use this usage, but I have heard many, many people use automaton for singular and automata for plural, as it is in Greek (where the word came from), and that's what Oxford and Webster have. I'm reverting your changes. —Keenan Pepper 16:59, 22 October 2005 (UTC)

Heck, just Google the word automatas. Every single one of the first 20 hits is in Spanish, because autómatas is a legitimate Spanish word. The absense of English hits is strong evidence of automatas being a bogus word in English, which it is, because automata is already plural. —Keenan Pepper 17:18, 22 October 2005 (UTC)

I have no specific knowledge on the subject but basing your evidence on the first 20 Google hits being in Spanish is pretty shaky, Keenan Pepper. Try this search. Afelton 23:17, 23 October 2005 (UTC)

OK, point taken. But just because other people use it doesn't mean we should. I still have Greek, Oxford, Webster, and Wolfram on my side. —Keenan Pepper 01:40, 24 October 2005 (UTC)

[6]: I get over 673k of hits on automatas in spanish, and about 28k for the same word restricted to English. 216.234.170.67 01:03, 2 August 2006 (UTC)

Practical Infinity. Bounded Chaos.

It consists of an infinite, regular grid of cells... - I don't think it has to be infinite. Later the text brings up the toroid, implying "they don't have to be infinite", so why then should the definition include infinity? Btw.: Much simpler than a toroid would be a simple ring as cyclic boundary condition of a 1d CA. OK, it's also more boring, but maybe it would be easier to understand for newbies. - 134.91.151.17 10:17, 7 April 2006 (UTC)

Yes, but that ring must be permitted to have infinite length. Dysprosia 10:20, 7 April 2006 (UTC)

[7]: A sphere might explain the wrapping nature more simply. I haven't gone into cells very deeply with fractint (just a few par files). I can say that infinity plays a part in many fractal definitions. For example, it's difficult if not impossible to prove that a Mandelbrot point will never escape, given infinite iterations, unless it's 0,0. Yet, a guy who noticed "periodicity" in some points manajed to get his "periodicity checking" method coded as the default in fractint. It's very messy on inversions of the Mandelbrot set at points that are 'sheltered' (majorly surrounded by points outside the set). 216.234.170.67 01:03, 2 August 2006 (UTC)

Neighborhoods?

Should there be a section or a new page describing the neighborhoods of cellular automata? There's already a page for the Moore neighborhood but nothing on the von Neumann neighbohood and no links to anything else. Actually, there's hardly any mention of it anywhere.

Actually, I have been working on a complete description of von Neumann cellular automata, and this will include a clear discussion of the neighborhood and state-transition function. William R. Buckley 06:22, 11 July 2006 (UTC)

Universality

[8]: I think some clarification of what universal means in simulations might be in order. I didn't find fractal anywhere on the page. Someone might replace a few "CAs" with "automata", and "cells". I think it's given in the title that they are "simulated cells" (Then again, that might be a useful search term). CA: CatecholAmine. http://www.fractint.org/ 216.234.170.67 00:14, 2 August 2006 (UTC)

Matthew Cook has a wikipedia page which this page should link to (and vice versa). —Preceding unsigned comment added by 71.201.171.211 (talk) 00:16, 20 November 2008 (UTC)

Article Architecture

I like the inclusion of references and links to applications of cellular automata. However, the current architecture of the article makes such inclusion problematic. It seems to me that a separate article should be created, to discuss the various applications thereof: Cellular Automata Applications. William R. Buckley 18:03, 7 September 2006 (UTC)

IMHO, the article as a whole is quite long and rambling, and would benefit from some rather bold splitting. The problem you mention is just one of the symptoms. —Ilmari Karonen (talk) 21:24, 7 September 2006 (UTC)

CA languages

What languages are there for defining cellular automata? The one I know of is ALPACA; I tried to save its article here from deletion without success, but I still have a backup of it. I'd even begun to figure that it would be worth mentioning ALPACA here before it was deleted. But what do people think here? And does anybody know any others? -- Smjg 11:39, 5 October 2006 (UTC)

Revision - Reversion of 20061217

Here it seems appropriate to pipe in. Ilmari, the section

"These 256 CAs are generally referred to using Wolfram notation, a standard naming convention invented by Wolfram."

should be reduced to

"These 256 CAs are generally referred to using Wolfram notation."

with the stuff of who invented the notation to be left to the referenced article, *Wolfram notation*.

Retention of the problematic is not a virtue. On the other hand, your good sense to know bad writing is much appreciated. William R. Buckley 21:04, 17 December 2006 (UTC)

Yes, in fact I think most of that section could be moved elsewhere; we already have separate articles on rule 30 and rule 110. Much of the rest duplicates the Wolfram notation article; I've been thinking it might be a good idea to start an article on elementary cellular automata, and maybe merge the Wolfram notation article there. Or maybe not. The reason I haven't actually done anything about this except complain to no-one in particular is simple laziness and lack of time, plus the fact that I'd need to find my copy of ANKoS in the big pile of stuff in the attic. I'll get around to it eventually, assuming no-one else does it first, but I make no promises as to when that "eventually" might be. —Ilmari Karonen (talk) 01:21, 21 December 2006 (UTC)

Molluscan cellular automatons

The assertion that molluscan pigment patterns are produced by cellular automatons is an intriguing idea. It closely resembles a hypothesis presented in Wolfram's book, which references Conrad Waddington and Russell Crowe (1969); Bard Ermentrout, John Campbell, and George Ostler; and Hans Meinhardt. To this list could added one more paper from 1990. However, so far as I know no one has claimed biological evidence to support the idea - they simply present various computer simulations which resemble certain shells. Although there is very little known about the molecular biology of mollusc pigment patterning, I would find it fairly persuasive if someone identified a species for which different races or mutants followed different, recognizable cellular automaton rules. Does any such data exist? If the only true source of the section is Wolfram's book, this needs to be properly acknowledged and the claims presented should be reduced to those he has made. Mike Serfas 17:50, 20 December 2006 (UTC)

I agree. The pretty patterned Conus shell is a good poster child but I could not find a solid reference about the pigmentation being a biological implementation of CA. The only explicit reference to a biological basis I came upon was negative:

"Mathematical modeling of pigmentation patterns was pioneered in 1969 by Waddington and Cowe [35], who reproduced patterns ... using cellular automata. A similar formalism was applied by Baker andHerman [1], and Wolfhrn [37]. According to Murray [22, page 506], these models had no basis in the underlying biological processes involved in the mollusc’s growth." (Fowler et al., Computer Graphics 26(2),379-,1992)

A more thorough treatment can be found in the book "The Algorithmic Beauty of Sea Shells" by Hans Meinhardt (partly available online in google books). It doesn't seem to me that CA are sufficient to explain the underlying mechanisms. On the other hand, the assertion in the existing wiki article is quite strong:

"Each cell secretes pigments according to the activating and inhibiting activity of its neighbour pigment cells, obeying a natural version of a mathematical rule"

Can someone cite the original reference for this claim? --128.175.195.178 19:08, 6 November 2007 (UTC)

Commercial sites and the wikipedia external link guidelines

wikipedia:External_links has the following guidelines:

"Links normally to be avoided ...

3 Links mainly intended to promote a website.

4 Links to sites that primarily exist to sell products or services."

Here is a quote from the opening sentence of a [[9] press release] about a company with an external link embedded in this article:

"... (in business since mid-1997) exists primarily to market the software ...".

I am removing the link for violating item four above. 66.42.71.67 20:20, 27 January 2007 (UTC)

Strange reversion of a justified deletion

The following fragment has absolutely no sense in the CA context:

For example, take a 2-sphere, and attach a handle between two nearby points on the equator; because this manifold has Euler characteristic zero, we may choose a continuous nonvanishing vector field pointing through the handle, which in turns implies the existence of a Lorentz metric such that the equator is a closed timelike geodesic. An observer free falling along this geodesic falls toward and through the handle; in the observer's frame of reference, the handle propagates toward the observer. This example generalizes to any Lorentzian manifold containing a closed timelike geodesic which passes through relatively flat region before passing through a relatively curved region. Because no closed timelike curve on a Lorentzian manifold is timelike homotopic to a point (where the manifold would not be locally causally well behaved), there is some timelike topological feature which prevents the curve from being deformed to a point.

I tried to remove it, but someone (check the logs) has reversed the deletion almost instantaneously. I even suspect it to be a robot. —The preceding unsigned comment was added by 85.58.143.31 (talk) 20:09, 13 February 2007 (UTC).

I finally decided to remove it again. —Preceding unsigned comment added by 85.58.143.31 (talk • contribs) 20:56, 13 February 2007

WikiProject Cellular automata

Is any one interested in creating a WikiProject to work on the various CA-related articles? Alpha Omicron 23:50, 10 April 2007 (UTC)

I'm working on other areas of WP at the moment, so can't really help actually set up the project, but I am interested in the continued health of the CA articles, and would certainly participate in discussions for such a project. I think it's a good idea because the area is a little remote from the concerns of the larger math and CS projects. —David Eppstein 00:22, 11 April 2007 (UTC)

My thinking exactly. I think the scope is manageable and it seems there is a large enough pool of potential members. Alpha Omicron 13:35, 11 April 2007 (UTC)

I've gone ahead and added it to Wikipedia:WikiProject_Council/Proposals, those interested can add their names there. When we have six or seven names someone can make a page for the project. Alpha Omicron 14:06, 11 April 2007 (UTC)

I've left messages on lots of userpages, but it looks like it's just the three of of for now. A vote on whether to plow forward with WikiProject Cellular automata? I vote to move forward with it. Alpha Omicron 00:58, 22 April 2007 (UTC)

Subcategory for people?

I've been cleaning up Category:Cellular automata and think it would be appropriate to have a subcategory listing people known in part for their contributions to the theory or applications of cellular automata. We already have one person listed as such in the main category (Joseph Nechvatal) but we could add Edward Fredkin, Stephen Wolfram, Bill Gosper, John Conway, etc., so I think there's a good quantity of articles that can be included. Where I'm at a little of a loss, though, is what to call it. The best I can come up with is Category:Cellular automatists. Other thoughts I had were Category:Researchers in cellular automata or Category:Cellular automaton researchers but that doesn't seem to really fit Nechvatal, an artist who uses CA in his art. Anyone else have any ideas? —David Eppstein 22:06, 20 April 2007 (UTC)

I suppose cellular automatists fits best, but doesn't sound so great. Don't forget John Von Neumann. Alpha Omicron 02:12, 21 April 2007 (UTC)

I agree, cellular automatist may I be. William R. Buckley 08:56, 21 April 2007 (UTC)

Ok, cellular automatist it is. The phrase doesn't have many ghits, but some of the ones it has are in reliable pubs, so I think we're safe from accusations of neologism. —David Eppstein 18:42, 21 April 2007 (UTC)

Another related term is Lifenthusiast but it's too specific to one rule... —David Eppstein 02:25, 21 April 2007 (UTC)

Overview

I do not believe the first sentence in the overview qualifies under the Wikipedia guidelines: [10]

Evoloop

The removal of the Evoloop link, even though it does redirect to Langton's Loop, is a very bad decision, for the Evoloop is a particular example of self-replicating loop, with character that goes beyond the character of Langton's Loop. Perhaps an article describing the details of the Evoloop should be added to the Wikipedia. However, references to the Evoloop, however cursory, should not be removed from Wikipedia simply because of correspondence to a redirection. William R. Buckley (talk) 16:46, 20 August 2008 (UTC)

I'm afraid that doesn't really make sense. The whole point of adding a hyperlink is to provide more example. It's a common stylistic form, reached by consensus, to avoid self-redirecting internal links.  Xihr  01:38, 21 August 2008 (UTC)

Rule vs. Function

I replace the word 'function' in the opening paragraph with the word 'rule' for understandability. William R. Buckley has pointed out to me however that 'function' is a standard in the literature on the subject. 'Function' is more correct mathematically as well. But I think a higher priority in the lead paragraph is that a reader with little knowledge of formal mathematics should be able to understand the general idea of the topic. So I agree that 'function' should be used throughout most of the article, especially in a formal definition, but I believe 'rule' is better for the lead section.--RDBury (talk) 14:31, 15 May 2009 (UTC)

I am going to make a slight change to the wording of the sentence(s) involved. I will retain the use of word *rule* but will indicted the more correct term within parenthesis. Your review is invited, and should you find reason to revert, please indicate such reason below this message. I do very much appreciate your participation in this exchange. William R. Buckley (talk) 19:12, 16 May 2009 (UTC)

The adjustments I made also address my concerns for some edits made by David Eppstein, that the state transition function be static, and that it be applied to all cells synchronously. These restrictions are not evocative of available literature. For instance, asynchronous cellular automata have been studied by Zielonka(1989), Kuske(1998), and Diekert and Muscholl(1995). Deadman et al.,(1993) address the topic of dynamic transition rules. William R. Buckley (talk) 19:29, 16 May 2009 (UTC)

Alternative geometries

I took out a sentence referring to CA's on hyperbolic tilings. This may be an interesting generalization but I've never seen it mentioned in the literature. There are many tilings of the plane that have the required symmetry as well, for example the Cairo pentagonal tiling. Again, while interesting possibilities, most of these have not been studied in the literature (as far as I've seen at least). With a little thought, other generalizations are possible, but there is no shortage of CA's to study without such extensions so it's doubtful whether they should mentioned in the article.--RDBury (talk) 16:02, 15 May 2009 (UTC)

Nomenclature

Cellular automata is not always a properly plural form of cellular automaton. The individual cells are clearly cellular automatons. The collection of a set of such cells are in toto cellular automata, and this is the only proper plural usage. The pattern of cells defines a cellular automaton, a machine, composed of parts. Alternative usage of these terms (cellular automata, cellular automaton) adversely affects the quality of this article. William R. Buckley (talk) 13:01, 31 August 2009 (UTC)

Unique Thing

I found that Rule 122 is fairly unique, in that it is VERY predictable when in a simple starting position, but has Class 3 behavior when placed in random order. In simple conditions, it acts exactly like Rule 250, which exhibits class 1 behavior. I think thats pretty cool...... Does it deserve a mention in the article? WolframAlpha could be the source. 74.199.8.90 (talk) 22:16, 22 December 2009 (UTC)