275
правок
Изменения
м
→Эквивалентность линейного клеточного автомата машине Тьюринга
{{Теорема
|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. Окрестность клетки]]
