Talk:Von Neumann cellular automata

From Wikipedia, the free encyclopedia

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)

• 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)

• • 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)

[edit] 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)

[edit] 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."