Talk:Neighbourhood

This entry is quite a bit longer than those for the other neighborhoods because they seemed to be rather skimpy. It would be nice if the discussion could be spread out equally among the other pages, or - better yet - unified under the simple heading Neighbo(u)rhoods. While encyclopedia articles are generally very much shorter than textbooks, I have generally found the explanations given in many of the articles here too short to convey a clear idea of what they are about. There must be a balance somewhere - a concise explantion and lots (not too many) of references.

Thanks for cleaning up some small errors I was intending to come back and fix. However I think that quiescent is usually reserved for an unchanging background (compare vacuum and Cook's ether for Rule 110), and my motive in splitting 29 (not 27) was to give an idea of why there were so many states without defining them all.

There are ten quiescent states, including the ground state U, the confluent state C₀₀, the four passive OTSs and the four passive STSs. If the universe contained any configuration of these ten cells, it would remain unchanging. --Calcyman 09:59, 26 October 2009 (UTC)

Still pending: Block cellular automaton and its relation to the Margolus neighborhood.

Wikipedia, anyone ?

I found pics in Wikipedia that may offer a nice illustration of the clear but not so clear concept of M. N. : http://upload.wikimedia.org/wikibooks/en/thumb/d/d1/Cellular_automata_unaligned_rectangular_neighborhood.png/150px-Cellular_automata_unaligned_rectangular_neighborhood.png What do you think ? Is it kosher to use WP pics like that ? --Methodood 16:14, 23 October 2009 (UTC)

There is a fundamental artistic problem of how to present half-integer neighborhoods and their evolution in a two-dimensional automaton. One-dimensionally, successive lines of evolution can be centered beneath their predecessor with pleasingly symmetrical results. The CAM machines kept two image planes and alternated their exhibition, achieving much the same result. Explaining how this is done by a program using an integer lattice is not so easy, nor is the relation of rules like 2x2 to Margolus-Toffoli. It might be a good idea to work this out before inserting more text on this page.

The cells in a Margolus neighbourhood remain in the same positions, unlike (for example) the neighbourhood of the XOR rule. The Margolus neighbourhood is a partitioning scheme, rather than a classic neighbourhood, which gives it certain useful properties. Among them is the ability to have matter conservation laws, like in Fredkin and Toffoli's BBM model. --Calcyman 09:59, 26 October 2009 (UTC)

Is the opposite of kosher trefft? The canonical WikiPedia has a very poor presentation of this neighborhood question, and there seems to be little point of just copying it. Quite aside from all these issues of copyrights and copylefts, one should question whether the material is worth copying (or cross-referencing) in the first place. My vote is, NO! Why not go over and edit WP and avoid the problem? Maybe to avoid an edit war, or maybe lack of interest.

Still pending - creating an entry on blocking and relating block automata to the other styles. Also mostly an artistic issue.

As for that particular figure, surely there is a better one; the figure itself appears at many Internet sites. True, it shows the displacement and centering of alternate square lattices, but a better depiction of a connection to Life and the Moore neighborhood is needed. Pixel boundaries (Life cells) overlap between generations - does executing 2x2 in Golly show this (I can't really check)? If only alternate generations are shown, can initial conditions be assigned at will to both odd and even generations at the start? And how to incorporate block automata which have 16 rules replacing a 2x2 square by a full square, not by just generating one single cell? Are these Margolus automata or not? Untill there is a good resolution of these doubts, wouldn't it be better to leave the page as it is now?

Block cellular automata are defined in the Moore neighbourhood, but they can emulate certain Margolus rules. There are 64 such rules, by the way, not 16. --Calcyman 09:59, 26 October 2009 (UTC)

Following our beloved British English, sheep can be singular, referring to an individual animal, plural referring to several of them, or collective referring to the entirity of sheepdom. So it is here, rule tells what to do with a a single neighborhood; given the states of four cells, a rule tells what to do about it. A Rule, which may have a christian name such as Conway's Life, or a mere number such as B34/S67, tells what to do whatever the contents of its neighborhood may be. To use these terms interchangeably is to commit the same sin as confusing a Function f with its value f(x). I took the figure in question from a website which specializes in such matters; each of 16 arrangements of the four cells in a 2x2 square got its r(lc)ule, one for each, 16 in total. Agreed that there are 64 R(uc)ules, which may or may not have been baptized. Presumably one of them is the billiard ball computer.

Should the renaming of the page constitute an endorsement for making it truly comprehensive? And perhaps retiring those other two? Besides what we already have, there are Fredkin's rules for mapping the sterechron - also in the expectation of constructing reversible rules?

The article is of very low quality

This article is of very low quality. The topic is neighborhoods of cellular automata, yet most of the content is off-topic. The sections “States”, “Tiling”, “Rules” belong to a general discussion of cellular automata, not to a discussion specific to neighborhoods. Moreover, the only section that is on-topic, “Neighbourhood”, is very poorly written and plagued with vagueness. Here is just an example of such a vagueness:

To make better sense of the use of topological discs, consider that for a von Neumann neighborhood, a cell's evolution then depends on a minimal (but symmetric) sampling of the surrounding dimensions, while the Moore neighborhood achieves a maximal sampling.

“Minimal” in what sense? The term “minimal sampling of the surrounding dimensions” was never defined in the article, and there is no standard definition for this term in mathematics. Therefore this utterance is meaningless.

Also, the mention of L_p functions is an unproductive digression. Only L_∞ and L₁ are relevant because they are used in several explicitly defined cellular automata (e.g. John von Neumann original cellular automaton and Conway's Life); the rest are not.

Marioxcc (talk) 14:51, 4 July 2017 (UTC).

I agree, re: the article being of low quality in general. Would you like to take a stab at refactoring it? You've done an excellent job on Cellular automaton, and clearly know a lot more about the mathematical background that others (like me).

I think the bit about L^p norms is interesting, though; there's no reason why these couldn't be used to determine neighborhoods, even if this hasn't been done so far (hasn't it? I would actually not be surprised if there was something out there in the literature, somewhere), or if current software doesn't support it. -- Apple Bottom (talk) 16:45, 4 July 2017 (UTC)

Sorry for the delay in answering. I did did not see your message while I was still editing in my previous session.

I think that refactoring is not necessary because I added almost all the information that was in this article to cellular automaton before making the redirect. Refactoring the article would simply duplicate that information and the effort.

I intentionally omitted the L functions because I don't think they are important. I get what you say, that they are one possible way to define a neighbourhood. However, there are infinitely many possibly ways to define a neighbourhood and we can not describe them all. We have to “draw the line” somewhere. The generalized von Neumann and Moore neighbourhood cover all the cellular automata that I have seen described in the literature (except for triangular neighborhoods, but those can not be expressed as a neighborhood in the grid; although they can be simulated).

Do the neighborhoods defined through the L functions have any desirable property that the Moore and von Neumann neighbourhood do not have?

Regards and thanks. Marioxcc (talk) 21:45, 5 July 2017 (UTC).

I don't know if they have any desirable (or undesirable but interesting) properties, or if there's any literature about them. I merely assumed that since they were being discussed here, the latter would have to be true. If not, perhaps it's an avenue for future research.

The bit about there being infinitely many possible ways to define a neighborhood is well-taken. Perhaps this could itself be added to the article; of course it's trivially true (just consider Moore neighborhoods of arbitary range), but it's also true that there's infinitely many "families" of neighborhoods.

For refactoring, you could probably just cut everything from this article that doesn't belong in it: move it elsewhere if it isn't already covered, otherwise just remove it entirely.

And I see you've already done that. Good work, thanks again! Apple Bottom (talk) 10:55, 6 July 2017 (UTC)