Skip to main content
Added more specific information.
Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Edit: I think your discovery fits into an existing terminological framework (though this does not give much of an explanation):

Remarks.

  • Note that your rule that the vertex-to-be-updated does not contribute its current value to the sum which determines its next state can be 'simulated'/'is an instance of' the definition of 'totalistic cellular automaton' on this website. I am only speaking about your question for paths; and I take it that you are working over the ring $\mathbb{Z}/(n)$, where $(n)$ denotes the principal ideal generated by $n$.

I assume you are working with the path graph $0\text{-}1\text{-}\dotsm\text{-}n-1$.

I write $v_i^{t}$ for the value of vertex $i$ at time $t$.

For $0<i<n-1$ you require1

$\mathbf{v_{i}^{t+1} + (n)} = v_{i-1}^{t}+v_{i+1}^{t} + (n)$ ${}\qquad\qquad$ (global.rule)

At the boundaries you require (which is a serious complication when it comes to making a precise connection with the existing literature on cellular automata)

$\mathbf{v_{0}^{t+1} + (n)} = v_{1}^{t} + (n)$ ${}\qquad\qquad$(left.boundary.rule)

$\mathbf{v_{n-1}^{t+1} + (n)} = v_{n-2}^{t} + (n)$ ${}\qquad\qquad$(right.boundary.rule)

Now the point I would like to make is that your (global.rule) just is one of the hundreds upon hundreds of rules known and documented by Wolfram. I did not try to find out which decimal number they have assigned to your rule. Nor did I try to find out whether Wolfram has a classification for rules which suddenly change at the boundaries (such as yours do). Let me just mention that this violates what

Carsten Marr, Marc-Thorsten Hütte: Outer-totalistic cellular automata on graphs. Physics Letters A 373 (2009) 546-549

in Section 2 call 'Homogeneity'.

Let me also mention that looking into K. Salman: ANALYSIS OF ELEMENTARY CELLULAR AUTOMATA BOUNDARY CONDITIONS,

and contacting the author, seems a relevant thing to try.

1 I use the boldface for readability only; it is not inteded to have mathematical meaning.

Edit: I think your discovery fits into an existing terminological framework (though this does not give much of an explanation):

Remarks.

  • Note that your rule that the vertex-to-be-updated does not contribute its current value to the sum which determines its next state can be 'simulated'/'is an instance of' the definition of 'totalistic cellular automaton' on this website. I am only speaking about your question for paths; and I take it that you are working over the ring $\mathbb{Z}/(n)$, where $(n)$ denotes the principal ideal generated by $n$.

I assume you are working with the path graph $0\text{-}1\text{-}\dotsm\text{-}n-1$.

I write $v_i^{t}$ for the value of vertex $i$ at time $t$.

For $0<i<n-1$ you require1

$\mathbf{v_{i}^{t+1} + (n)} = v_{i-1}^{t}+v_{i+1}^{t} + (n)$ ${}\qquad\qquad$ (global.rule)

At the boundaries you require (which is a serious complication when it comes to making a precise connection with the existing literature on cellular automata)

$\mathbf{v_{0}^{t+1} + (n)} = v_{1}^{t} + (n)$ ${}\qquad\qquad$(left.boundary.rule)

$\mathbf{v_{n-1}^{t+1} + (n)} = v_{n-2}^{t} + (n)$ ${}\qquad\qquad$(right.boundary.rule)

Now the point I would like to make is that your (global.rule) just is one of the hundreds upon hundreds of rules known and documented by Wolfram. I did not try to find out which decimal number they have assigned to your rule. Nor did I try to find out whether Wolfram has a classification for rules which suddenly change at the boundaries (such as yours do). Let me just mention that this violates what

Carsten Marr, Marc-Thorsten Hütte: Outer-totalistic cellular automata on graphs. Physics Letters A 373 (2009) 546-549

in Section 2 call 'Homogeneity'.

Let me also mention that looking into K. Salman: ANALYSIS OF ELEMENTARY CELLULAR AUTOMATA BOUNDARY CONDITIONS,

and contacting the author, seems a relevant thing to try.

1 I use the boldface for readability only; it is not inteded to have mathematical meaning.

Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

I do not consider the following an answer, most especially since I take you main question to be very focused one: to mathematically explain the 182. Yet I think pointing out the relevance to what is called 'totalistic cellular automata' is on-topic. The comment boxes are too small to appropriately do so.

The most relevant technical terms related to your question known to me are 'totalistic cellular automaton' and 'isotropic rules', as in e.g.

Emmanual Sapin, Olivier Bailleux, Jean-Jacques Chabrier: Research of a Cellular Automaton Simulating Logic Gates by Evolutionary Algorithms; in the proceedings of 'Genetic Programming: 6th European Conference' The most relevant published article known to me is

Carsten Marr, Marc-Thorsten Hütte: Outer-totalistic cellular automata on graphs. Physics Letters A 373 (2009) 546-549

The definitions therein do not really meet your needs though. This already begins with 'states' being only allowed to be elements of $2$ in loc. cit. I also cursorily checked whether some of your numbers show up in loc. cit., without finding any. Yet I think you might make progress by looking into this part of the literature, or contacting the authors of loc. cit.

Also very relevant (especially since it allows integer valued states, yet again not answering your question, is Dan Gordon: On the Computational Power of Totalistic Cellular Automata. Mathematical Systems Theory. 20, 43-52 (1987).

Again, there are the expected slight mismatches, notably that loc.cit. includes the value of a cell whose next state is to be computed into the sum which determines the next state. And philosophically, loc. cit. contains results which are sadly rather discouraging when it comes to mathematically explaining you discovery (where 'mathematically explaining' here means 're-generating your empirical discoveries from the traditional logical primitives of modern mathematics', which would be the most desirable outcome), since it contains results of computational universality.

And yet again, loc. cit.seems very close and contacting the author of loc. cit. seems a good thing to try.