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