Изменения

Перейти к: навигация, поиск

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

11 байт добавлено, 22:07, 21 декабря 2015
м
Эквивалентность линейного клеточного автомата машине Тьюринга
{{Теорема
|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. Окрестность клетки]]
275
правок

Навигация