Материал из Викиконспекты
Определения
| Определение: |
Клеточным автоматом [math]A[/math] размерности [math]d[/math] называется четверка [math]\lt {Z^d}, S, N, \delta\gt [/math], где
- [math]S[/math] — конечное множество, элементы которого являются состояниями [math]A[/math].
- [math]N[/math] — конечное упорядоченное подмножество [math]Z^d[/math], [math]N=\{{n_j}|{n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}[/math], называемое окрестностью (neighborhood) [math]A[/math].
- [math]\delta : S^{n+1} \rightarrow S[/math] — функция перехода для [math]A[/math].
|
| Определение: |
| Линейным клеточным автоматом (ЛКА) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из [math]2 \cdot r + 1[/math] клеток,
находящихся на расстоянии не более [math]r[/math] от данной. |
Другое определение линейного клеточного автомата
| Определение: |
| Линейным клеточным автоматом [math]A[/math] назовем бесконечную ленту, в каждой клетке которой записан некоторый автомат. На вход автомату в клетке [math]i[/math] подается
вектор из состояний автоматов в клетках с [math]i - r[/math] по [math]i + r[/math] включительно. |
| Утверждение: |
Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат. |
| [math]\triangleright[/math] |
|
Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как [math]D[/math]. Построим автомат [math]B[/math] следующим образом: множеством вершин [math]B[/math] будет объединение множеств вершин автоматов из [math]D[/math], переходы между вершинами [math]u[/math] и [math]v[/math] будет совпадать с переходами [math]D_i[/math], если [math]u[/math] и [math]v[/math] соответствуют вершинам из [math]D_i[/math], иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата [math]D_k[/math], который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением [math]D_k[/math]. |
| [math]\triangleleft[/math] |
