436
правок
Изменения
Definition fixed
= Базовые определения =
{{Определение
|definition=
'''Клеточный автомат''' представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии, множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$. Исходно все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от 1 до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$.
}}
{{Определение
|id=moore_neighborhood
