Talk:Von Neumann cellular automaton

This article was nominated for deletion on 2 November 2005. The result of the discussion was keep.

It is good that this article was kept. There is much information that can be added, and same will provide others with a source that is more accessible than are either of the published books respecting the topic of von Neumann cellular automata. If any reader of these comments is familiar with the mechanisms of constructing and including graphical images, please post details, as same will improve the quality of this article. William R. Buckley 19:11, 4 February 2006 (UTC)[reply]

OK. I put in a bunch of detail, enough to mke one's own simulation of the thing... no diagrams though! Perhaps someone could contact Pesavento, the author of one of the online articles linked in Universal Constructor, for permission to use his diagrams? I don't really feel like making new ones at the moment! brain 06:36, 19 November 2006 (UTC)[reply]

- Pesavento's work is not in the von Neumann rule-set. Similar but no cigar. Other sources exist, like Renato Nobili or myself; we both work in the von Neumann rule-set. I strongly argue that the two systems, von Neumann and Nobili, should have articles with crosslinking. William R. Buckley 18:39, 21 November 2006 (UTC)[reply]

Symbol Set

The characters used for sensitised and confluent states are beautifully rendered. It will probably be a bit more difficult to find the single and double tailed arrows for the transmission states. I use Lucida Bright Math Symbol. It would be nice if a font could be created, being tightly monospaced and representing the 29 vNCA states.

The symbols shown are consistent with von Neumann's choice, and therefore a bit overdone. In practice, the digits of the confluent state are more practical as dots, periods, one on each side of the C symbol. The sensitised states have a similar simplification, using dots to represent the signal input. Here, I am speaking more of simplifications that facilitate efficiency (like readability) within simulation software. In the software of Renato Nobili, one bits are represented by a color change to the state symbol, a brightening of the color used for zero bits. William R. Buckley 20:50, 18 November 2006 (UTC)[reply]

Succinct Description of States and Transition Rules

The following is excerpted from the paper Amar and I wrote in 2005

  Constructibility of Signal Crossing Solutions
    in von Neumann 29-State Cellular Automata

    William R. Buckley and Amar Mukherjee

and is a very succinct description of the states and interactions thereof. I give this here so that others may find inspiration to reduce the space now (20061118) employed. I have removed the special symbols found embedded within the text of the paper.

"Von Neumann cellular automata are characterized by a two-dimensional, rectilinear lattice network of finite state automata (the cells), each identical in form, function, and association, as specified by a set of states, a set of rules for the transition of cells between states (the state transition function), and a grouping function that places each cell at the center of a neighborhood of adjacent cells (specifying the set of cells operated upon by the state transition function in the computation of state transitions). All cells transition their state synchronously.

"States are grouped into five categories; a ground state, the transition states, the confluent states, the ordinary transmission states, and the special transmission states. The last three categories have an activity property, while the last two categories have the property of direction. Activity corresponds to carried data, it being transmitted between states at the rate of one bit per application of the state transition function. Confluent states have the additional property of a one-cycle delay, and so hold two bits of data. The direction property indicates the flow of data between states. Ordinary and special transmission states have an antagonistic relationship, with mutually directed active cells of each causing the annihilation of the other, to yield the ground state. Active special transmission states also yield confluent state annihilation. Confluent states accept data from ordinary transmission states, perform a logical AND on the inputs, and transmit data to both ordinary and special transmission states. Ordinary and special transmission states logically OR inputs. An ordinary transmission state accepts input only from like states, and from adjacent confluent states. Special transmission states accept input likewise. Confluent states pass data to any adjacent transmission state not pointed at the confluent state. Data are not transmitted to transmission states against the direction of those transmission states. For instance, two ordinary transmission states pointing at each other do not exchange data. Instead, the data is simply lost. Data held by a confluent state is lost if there is no adjacent transmission state not pointing at the confluent state."

Is something missing?

"Data passes from cells in the ordinary transmission states to other cells in the ordinary transmission states, according to the direction property (in the cell's direction only)"

So the pulse moves from a given OTS cell in the direction of that cell's arrow. This means that, if two adjacent OTS cells are pointing at each other, any pulse that reaches one of them will hop between the two indefinitely.

However, this isn't what happens, at least in Golly, according to my experiments. Rather, if the cell in front of an excited OTS is an OTS pointed in the opposite direction, the pulse simply disappears. The same happens with STS cells opposed in the same way.

Has this rule been missed off the description here, or is it a bug in Golly's implementation? A lot of the pages of the reference are missing at the moment. — Smjg (talk) 20:41, 15 May 2014 (UTC)[reply]

No, data held by opposing OTS (such as -> <- ) will not exchange. Data cannot travel against the direction of a path; instead, it is simply lost. The proper references are von Neumann's papers and his posthumous work Theory of Self-Reproducing Automata, the work Essays on Cellular Automata edited by Burks, the papers of Nobili, and my papers. Golly works properly; last I looked, Nobili's software has state transition problems, these being well observed in carefully choreographed configurations. William R. Buckley (talk) 16:54, 17 May 2014 (UTC)[reply]