Линейный клеточный автомат, эквивалентность МТ

Материал из Викиконспекты
Версия от 21:28, 22 января 2012; 192.168.0.2 (обсуждение) (ЛКА: определения)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определения

Определение:
Клеточным автоматом [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], называемое окрестностью [math]A[/math].
  • [math]\delta : S^{n+1} \rightarrow S[/math] --- функция перехода для [math]A[/math].


Определение:
Линейным клеточным автоматом называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из [math]2 \cdot r + 1[/math] клеток, находящихся на расстоянии не более [math]r[/math].