Talk:Von Neumann neighbourhood

From LifeWiki
Jump to: navigation, search

Is there a Brooklyn neighborhood or a Queen's neighborhood? Does anyone know where this reference to taxicabs or New York bouroughs came from? Anyone who has ever wandered through Manhattan knows it's rectangular, not square. Do people in Australia, or Singapore or whereever know how New York is laid out? Why can't we respect Hamming, even though it was coding theory; or at least use L(1), L(2), L(infinite) and be Bourbakians.


Because Hamming distance, when generalised to the plane, is a different metric. All the points within a Hamming distance of one are the following:

.....o.....
.....o.....
.....o.....
.....o.....
ooooo*ooooo
.....o.....
.....o.....
.....o.....
.....o.....

This is obvious when the cells are converted into Cartesian coordinates -- these are the points that differ in only one coordinate.

Whereas the von Neumann neighbourhood refers to the orthogonally adjacent places, i.e. those within a Manhattan distance of one:

...........
...........
...........
.....o.....
....o*o....
.....o.....
...........
...........
...........


And for that matter, Manhattan distance is irrespective of whether the roads are in a rectangular or square arrangement; as long as all roads are orthogonal, the distance will be the same: the sum of the horizontal distance and the vertical distance.

And Queen's neighbourhood would be slightly ambiguous -- chess players would assume that it refers to all cells in the vertical, horizontal and diagonal lines that run through the central cell.

Yes, Manhattan distance is L(1), but the common name is more intuitive.


Regards, Calcyman 16:54, 29 January 2010 (UTC)


Let us not forget that Broadway runs diagonally across Manhattan. And anyone who bases a grid on a city map should beware Boston, whose streets arose from paving cow paths. However, one could wonder why this whole discussion of specialized neighbo(u)rhoods is in a Wikipedia devoted to Life, rather than in a more general context of cellular automata or dynamical systems; there is already a page dedicated to the general environment entitled "Neighborhood." Also, note the anomaly that the Hamming distance or whatever appears in a paragraph of an article on the von Neumann neighborhood referring to a property of a Moore neighborhood!
Using Internet to try to find word or phrase origins, It seems that Minkowski started off around 1900, that the L(p)'s refer to Lebesque, and that Tchebycheff (or was it Cebysev?) used a minimax of greatest among the least for approximations. However, the question at hand is whether "manhattan" is the best adjective. True, L(p) sounds too mathematical for life enthusiasts; equivalently taxicab or manhattan is much too cute. The best solution might to be to suppress these pages until such time that a better and more coherent discussion is available for each of them.
The broad subject would include not only the L(p) metric, of which only L(1) and L(infinity) seem pertinent, but sparse neighborhoods, historical neighborhoods, progressive neighborhoods, blocked neighborhoods, and so on. (Sparse to make iteration look more like composition, Historical to incorporate previous states of a cell, Progressive to incorporate recent changes in the formulation, Blocked to include Margolus, ..... )
Manhattan distance is the most widely accepted term for the L(1) metric. Admittedly, the name might be slightly imprecise, but it's better than (ab)using Hamming distance in this context.
As for the mistake on Wikipedia, I have also rectified that. Thanks for pointing that out; that's probably how it leaked on to the LifeWiki in the first place.
The different 'neighbourhoods' you have mentioned (e.g. 'Historical') are not neighbourhoods per se, but rather entire classes of rules (with the exception of 'blocked', which is another term for a partitioning scheme). Other neighbourhoods include the hexagonal neighbourhood (for the A2 lattice) and the three-dimensional analogues of the von Neumann and Moore neighbourhoods. For a comprehensive list of neighbourhoods, see the respective page on the Rule Table Repository: [1]
Isn't the whole discussion of neighborhoods more complicated than it needs to be? Part of the specification of a cellular automaton is the set in which it operates, which is commonly a crystallographic lattice, such as the cartesian plane with integer coordinates; that's where the cellular part comes from. Since a mapping, which is part of the process, is to be iterated, a generational index, usually regarded as time, could be included as an adjunct to the space. That could result in implicit, as well as explicit, definitions. Note how many words just saying this takes up; ordinary language doesn't get this complicated, but likewise doesn't encompass all the wierd possibilities.
Once we've got the space, there are neighborhoods. Although they are just subsets, there is a uniformity requirement. If the space is a lattice, they are related by symmetry; primarily translation (think of shift commuting dynamical systems). The space coule be a Cayley tree, neighbors established by linkage; many alternatives exist.
So much for definitions. In practice a particular cellular automaton might be chosen and studied in detail. Conway's Life is one of them, owing its interest to the illusion that its evolution could be understood, creating much entertainment and diversion. A more feasible alternative to understanding all properties of all cellular automata. Naturally this inherent curiosity encompasses variants and extensions, with an attendant challenge of parameterizing the alternatives. So we classify: shape and relative sizes of neighborhoods, dimension of neighborhoods, and so on. But wouldn't it be nice if this could be done in an orderly fashion?
To reply to one statement: "Historical" does not refer to what some LifeEnthusiast might have done in the past; it refers to the ordering implied by iteration, and to a rule of evolution which accounts for a certain portion of previous states. Fredkin's reversible rules are an example of this, and indeed Life can be taken as the reference rule for creating a reversible rule. Unfortunately, although the new rule is reversible, Life is not what it reverses.
What is this Google repository (reference 1)? Have they slurped up cellular automata too? I didn't see half-integer neighborhoods.
The variety of spaces for a cellular automaton is vast, indeed (uncountably?) infinite. As well as lattice grids, such as the square lattice, hexagonal lattice and FCC lattice, there are uniform nonlattice grids (e.g. triangular), and even totally aperiodic tilings such as the Penrose tiling. Life on Penrose tilings has been investigated, and forms the basis for a 50-page chapter in the upcoming Life book (Andy Adamatzky, 2010). Not to mention Lorentzian or hyperbolic spaces.
Classifying this infinite abundance of possible spaces is difficult, and I doubt that a systematic way exists to do so. If you think that you've found such a method, test it against the possible counter-examples in the above paragraph. I suppose that one might have to approach Penrose tilings from the 'quasicrystal' angle: define a lattice in a certain number of dimensions, and a hyperplane to intersect it.
As you've mentioned, the next step is to classify the neighbourhoods for each possible space. The square lattice alone has a massive variety of neighbourhoods, including the Moore neighbourhood, von Neumann neighbourhood and Margolus partitioning scheme. Again, the Rule Table Repository provides a more comprehensive list of neighbourhoods.
"Historical", when applied to cellular automata, almost invariably applies to a rule where the cells retain a "history" of whether they have been alive at any time. "Historical Life" (invented by Dave Greene), for example, behaves identically to Life, but has a third state to record whether cells have ever been alive. Gliders leave behind tracks in this third state.
The Rule Table Repository is a website, initially set up by Tim Hutton, but co-administrated by myself and four others.
Exactly what do you mean by 'half-integer neighbourhoods'?