105
правок
Изменения
Нет описания правки
{{Теорема
|definitionstatement=Для произвольной <tex>(m, n)</tex> машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, <tex>max(m + 1, n + 1)</tex> состояниями, эмулирующий эту МТ в реальном времени.|proof=Аналогично предыдущей теореме. Лента будет иметь следующий вид:
[[Изображение:Tape2.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в ЛКА]]
Доказательство аналогично предыдущей теореме.
}}
