36
правок
Изменения
Нет описания правки
==Определения==
{{Определение| id=cellularautomaton|definition='''Клеточным автоматом''' (КА) (англ. ''cellular automaton'') <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где
* <tex>S</tex> {{---}} конечное множество, элементы которого являются состояниями <tex>A</tex>.
* <tex>N</tex> {{---}} конечное упорядоченное подмножество <tex>Z^d</tex>, <tex>N=\{{n_j}|\mid {n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}</tex>, называемое '''окрестностью''' (англ. ''neighborhood'') <tex>A</tex>. В данном определении полагается, что клетка всегда принадлежит своей окрестности.
* <tex>\delta : S^{n} \rightarrow S</tex> {{---}} функция перехода для <tex>A</tex>.
}}
{{Определение|definition=
'''Линейным клеточным автоматом''' (ЛКА) (англ. ''linear cellular automaton'') называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,
находящихся на расстоянии не более <tex>r</tex> от данной.
}}
{{Теорема
|statement=
Для произвольной <tex>(m, n) </tex> машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
|proof=
[[Изображение:Mpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]]
Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.
==ЛитератураСм. также ==* [[Машина Тьюринга]]* [[Линейный ограниченный автомат]] == Источники информации ==* ''A.R. Smith III, '' {{---}} '''Simple Computation-Universal Cellular Spaces''', Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.* ''M. Delorme, '' {{---}} '''An Introduction to Cellular Automata''', July 1998. [[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]
