2
$\begingroup$

In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be something more complicated such as a function of the coordinates of the neighbor cells? (assuming there is a initial coordinate value give to at least one cell) So for example in 2-D if my neighbor to the left has coordinate $(x,y)$ my state will take a value $f(x,y)$ where $f$ is same for all cells.

$\endgroup$
  • $\begingroup$ Does your function $f$ depend in any way on the contents of the cells? $\endgroup$ – Yuval Filmus Feb 14 '14 at 21:51
  • 2
    $\begingroup$ You are asking two different questions: (1) Does the "cell alphabet" have to be finite? (2) Can the "transition function" depend on the coordinates? In both cases, you have to be careful about $f$: it should be computable. I don't know if these models have ever been studied. $\endgroup$ – Yuval Filmus Feb 14 '14 at 21:52
  • 1
    $\begingroup$ @YuvalFilmus $f$ depends on the coordinates of the neighbors and of the cell itself. So the color of the cell, I believe that is what you mean by cell alphabet, is given by $f$ and it is not a finite set. $\endgroup$ – Mat Feb 15 '14 at 16:09
1
$\begingroup$

Although Wikipedia mentions a finite set of states (http://en.wikipedia.org/wiki/Cellular_automaton), I'm sure you could find some interesting models that use infinitely many states. As you suggested, each cell could contain an integer, a continuous value between 0 & 1 (shade of grey), etc.

The idea of basing cell contents upon cell coordinates is interesting and unfamiliar. Of course, you'd have to also include some other inputs in the transition function if you want the pattern to change from step to step. This would create patterns that vary based on their location, which sounds fun to explore.

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! This answer is correct but rather superficial. Sure, one could do all of the things you suggest (which are all, fairly obvious) but what would be the consequences of doing any of those things. $\endgroup$ – David Richerby Jan 15 '15 at 10:46
1
$\begingroup$

I'm hardly the expert on these matters (my only point of contact being an artificial life class a while back) but a bit of googling found an interesting application of infinite-state cellular automata: "lattice-gas" cellular automata which apparently are used to solve PDEs by discretizing the diffusion equation. I'm strongly suspect there are more such applications, but like I said, I don't know much about them.

Note another book which says somethig rather obvious namely that the classic cellular automata lie at one extreme end of discretization with space, time and state being all discrete in CAs, while classic PDEs are at the other end with all three continuous. It also notes that there's no reason not to consider mixtures of these; it also gives additional synonyms you can google for continuous-state (but discrete time and space) cellular automata: coupled map lattices and lattice dynamical systems; on a quick look both terms seem to produce a fairly rich literature. So whether these are (properly) called cellular automata... it depends who you ask, I suppose. (Also I could not help myself LOL at the comment on next page in that book [which is at its 3rd ed.] "Obviously, this field is tempting for computer freaks".)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.