Изменения

|proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>d</tex> (из <tex>2d + 1</tex> клетки). Пусть в автомате клетки всего <tex>n</tex> состояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>O(n^{2d+1})</tex> состояний {{---}} по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на <tex>d</tex> влево, затем . Затем левый терминал будет переноситься на <tex>2d+1d</tex> вправоклеток влево, запоминая а для каждой клетки правее нового положения левого терминала будет запоминаться ее окрестность клетки, затем менять будет изменяться ее состояние текущей клетки соответственно поведению ЛКА , затем изменять окрестность и переходить к обработке клетки справа от текущей до тех пор. И так для всех клеток, пока не поменяет встретится правый терминал. При В этом, если головка обрабатывает терминал, то после этого случае необходимо сдвинуться влево или перенести его на <tex>d</tex> клеток вправо соответственно тому, какой терминал сейчас меняется, и поставить в текущую пустую клетку этот терминалпродолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТ будет эмулировать заданный ЛКА.