Automate cellulaire "Moitié moitié"

\( \require{bbox} \)

Axiomes

Soit un automate cellulaire unidimensionnel fonctionnant comme suit :

à la génération initiale, une seule cellule de masse non nulle existe ; sa masse est \( n \) (un entier) ;
lorsqu'on passe d'une génération à la suivante, chaque cellule conserve la moitié de sa masse (arrondie à l'unité supérieure) et donne la moitié de sa masse (arrondie à l'unité inférieure) à sa voisine de droite (qui l'additionne à sa propre masse).

Formellement, soit \( m_t(x) \) la masse située à l'abscisse \( x \) à la génération \( t \) ; les règles se transcrivent ainsi :

\[ m_0(0) = n \] \[ \forall x \in \mathbb{Z} \setminus \{ 0 \}, \mbox{ } m_0(x) = 0 \] \[ \forall t \in \mathbb{N}, \mbox{ } \forall x \in \mathbb{Z}, \mbox{ } \bbox[white, 10px, border: 3px solid red]{ m_{t+1}(x) = \left \lfloor \frac{m_{t}(x-1)}{2} \right \rfloor + \left \lceil \frac{m_{t}(x)}{2} \right \rceil } (1) \]

Expérimentations

Cet automate cellulaire s'implémente parfaitement avec un tableur. Exemples :

On finit toujours par arriver à une configuration faite de \( n \) cellules contigues de masse \( 1 \). Justification assez intuitive :

la masse totale reste constante ( \( n \) ) ;
les cellules dont la masse est non nulle restent toujours contigues (aucun 0 ne peut se glisser entre deux morceaux non nuls)
parmi les cellules de masse strictement supérieure à 1, celle située le plus à gauche a une masse qui ne peut que strictement décroître à la génération suivante ; toutefois cette masse ne peut descendre en dessous de \( 1 \) ; la cellule finit donc par valoir \( 1 \), qui est stable ;
en d'autres termes l'algorithme étale une tartine de \( 1 \) à gauche dont on sait que la taille va croître en un nombre fini d'étapes, tant qu'il reste une cellule de masse \( \gt 1 \) juste à la droite de la tartine ;
cela ne s'arrêtera que quand la tartine aura une taille \( n \).

Cette configuration faite de \( n \) cellules contigues de masse \( 1 \) est stable (= elle se perpétue indéfiniment). On peut la qualifier de configuration finale.

Soit \( a \) la fonction de \( n \) qui donne le nombre de générations nécessaires pour atteindre la configuration finale.

\( n \)	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
\( a(n) \)	0	1	3	4	6	8	10	11	13	15	17	19	21	23	24	26	28	30	32	34	36	38	40	41	43	45	47	49	51	53	55	56	58	60	62	64	66	68	70	72	74	76	78	80	82	84	86	87	89	91

Sur OEIS, j'ai créé l'entrée A300997 pour cette suite.

Observations / conjectures

pour tout \( n \), \( a(n+1) \) est égal à \( a(n) + 1 \) ou à \( a(n) + 2 \) — vérifié par ordinateur jusqu'à \( n = 300000 \) ;
c'est plus souvent \( +2 \) que \( +1 \) et la fréquence des \( +1 \) décroît avec \( n \)

Ces conjectures peuvent se modéliser comme suit : il existerait une fonction \( I \) à valeurs dans \( \{ 0, 1 \} \) telle que :

\[ a(n) = a(n-1) + 2 - I(n) \]

ou de manière équivalente,

\[ a(n) = 2 n - \sum_{k=1}^n I(k) \]

La fonction \( I \) est la fonction caractéristique des rangs \( n \) pour lesquels \( a(n) \) est \( a(n-1) + 1 \) au lieu d'être \( a(n-1) + 2 \). Par convention \( I(1) = 1 \) bien que \( a(0) \) ne soit pas défini.

Sur OEIS, j'ai créé l'entrée A305992 pour la liste de ces \( n \)... tant que la conjecture est vérifiée.

Les \( n \) dans cette liste seraient de plus en plus espacés.

Programmation et vue arborescente

Les tartines de uns à gauche n'ont aucune influence sur l'évolution future de ce qui se situe à leur droite. On peut donc (presque) les ignorer en écrivant des configurations simplifiées (exemple : [2] au lieu de [1,1,1,1,1,2]).

(Il faudra toutefois se souvenir que ces 1 existent, ne serait-ce que parce que la masse totale reste \( n \) et que la longueur de la tartine de uns augmentant, la configuration simplifiée est en fait glissante vers la droite).

Programmons un peu pour obtenir un arbre des différentes configurations simplifiées. C'est bien un arbre car le fait d'atteindre \( [1,1,1,\dots,1,1,1] \simeq [1] \) prouve que le graphe est enraciné en [1].

Implémentation en Prolog + Bash + Graphviz :


c(X, Y) :- Y is ceil(X / 2).
f(X, Y) :- Y is floor(X / 2).
add(X, Y, Z) :- Z is X + Y.

% Drops the final 0 in a list, if any.
drop0([], []).
drop0([0], []).
drop0([X], [X]) :- not(X = 0).
drop0([X, Y | T], [X | L]) :- drop0([Y | T], L).

% Drops the initial 1's in a list, if any,
% except if the list is just [1, ..., 1] in which case we keep [1].
drop1([], []).
drop1([X], [X]).
drop1([1, Y | T], L) :- drop1([Y | T], L).
drop1([X, Y | T], [X, Y | T]) :- not(X = 1).

% Computes the simplified successor list LL of L.
% "Simplified" in the sense that we remove the initial 1's.
succ(L, LL) :-
	maplist(c, L, C),
	maplist(f, L, F),
	append(C, [0], CC),
	append([0], F, FF),
	maplist(add, CC, FF, L1),
	drop0(L1, L2),
	drop1(L2, LL).

% Computes the number A of steps needed to reach [1] by iterating succ, starting from [N].
% Side effect: outputs L and its successors until [1] is reached.
a(N, A) :- go([N], 0, A).
go(L, N, NN) :-
	writeln(L),
	L = [1] -> (NN = N) ; (succ(L, LL), N1 is N + 1, go(LL, N1, NN)).
	
graphviz(L) :-
	L = [1] -> (true) ; (succ(L, LL), maplist(write, ['"', LL, '" -> "', L, '";\n']), graphviz(LL)).
	
graphviz :-
	tell('graphviz_lines.gv'),
	forall(between(1, 16, N), graphviz([N])),
	told.


GV="moitmoit.gv"

> $GV
echo "digraph G {" >> $GV
echo "	rankdir=\"LR\";" >> $GV
echo "	node [shape=\"none\" style=\"filled\" fillcolor=\"#BBBBBB\"];" >> $GV
echo "	edge [arrowhead=\"none\" arrowtail=\"normal\" dir=\"back\"];" >> $GV
n=1
while [ $n -le 16 ]
do
	echo "\"[$n]\" [label=\"[$n]\" fillcolor=\"#BBFFBB\"];" >> $GV
	(( n+=1 ))
done
cat graphviz_lines.gv | awk '
# remove duplicates while keeping order of first appearance
{
	if (!($0 in mem))
	{
		print $0;
		mem[$0] = 1;
	}
}
' >> $GV
echo "}" >> $GV

./dot_svg.bat $GV

Résultat :

On a choisi ci-dessus de se limiter à \( 1 \leq n \leq 16 \) pour rester lisible ; on pourrait pousser plus loin mais il n'est guère raisonnable d'aller plus loin que \( n = 200 \) avec l'implémentation actuelle (quelques minutes de calcul).

On visualise que \( a(n) \) est la profondeur du noeud \( [n] \) dans l'arbre (les [n] sont les noeuds coloriés en vert).

On visualise des choses me semble-t-il essentielles dans une tentative de démonstration de nos conjectures :

il y a une colonne vertébrale de noeuds : \( [1], [2], [2, 1], [2, 2], [2, 2, 1], [2, 2, 2], \dots \) ;
les \( n \) pour lesquels \( a(n) = a(n-1) + 1 \) semblent être ceux vérifiant la propriété : \( [n] \) est la première configuration qui (en évoluant) atteint un nouveau \( [2, 2, \dots, 2, 2] \) ;
pour ces \( n \), la chaîne qui va de \( [n] \) jusqu'à \( [2, 2, \dots, 2, 2] \) est en bijection évidente avec la chaîne qui va de \( [n-1] \) jusqu'à \( [2, 2, \dots, 2, 1] \) (avec un 2 en moins) ;
or ce \( [2, 2, \dots, 2, 2] \) se jette lui-même dans \( [2, 2, \dots, 2, 1] \), ce qui explique la longueur de chaîne augmentée de 1 ;

A poursuivre...

Equation aux différences finies partielles

On part de la formule :

\[ \forall x \in \mathbb{R}, \mbox{ } \bbox[white, 10px, border: 3px solid red]{ x = \left \lceil \frac{x}{2} \right \rceil + \left \lfloor \frac{x}{2} \right \rfloor} (2) \]

Appliquée à \( m_t(x) \), cette formule donne :

\[ m_t(x) = \left \lceil \frac{m_t(x)}{2} \right \rceil + \left \lfloor \frac{m_t(x)}{2} \right \rfloor \] \[ \bbox[white, 10px, border: 3px solid red]{ \left \lceil \frac{m_t(x)}{2} \right \rceil = m_t(x) - \left \lfloor \frac{m_t(x)}{2} \right \rfloor} (3) \]

En injectant (3) dans (1), on obtient :

\[ m_{t+1}(x) = \left \lfloor \frac{m_{t}(x-1)}{2} \right \rfloor + m_t(x) - \left \lfloor \frac{m_t(x)}{2} \right \rfloor \] \[ \bbox[white, 10px, border: 3px solid red]{ m_{t+1}(x) - m_t(x) = \left \lfloor \frac{m_{t}(x-1)}{2} \right \rfloor - \left \lfloor \frac{m_t(x)}{2} \right \rfloor } (4) \]

Si l'on note \( \Delta \) la différence finie avant et \( \nabla \) la différence finie arrière (comme sur Wikipedia), et si l'on met en indice la variable discrète \( t \) ou \( x \) suivant laquelle on effectue la différence finie, alors l'équation (4) peut s'écrire :

\[ \bbox[white, 10px, border: 3px solid red]{ \Delta_t \mbox{ } m = - \nabla_x \left \lfloor \frac{m}{2} \right \rfloor } (5) \]

Interprétation : l'évolution temporelle (future) de \( m \) en une position fixée (terme de gauche) est directement liée à l'évolution spatiale (arrière) de \( \left \lfloor \frac{m}{2} \right \rfloor \) en l'instant figé (terme de droite).

C'est en quelque sorte une équation différentielle partielle, mais discrète au lieu d'être continue. L'analogue continue serait, je pense, une loi de Fick.

Comment exploite-t-on une telle équation ?

LR, 15/04/2023.