Изменения

* Каждой конфигурации машины Тьюринга можно сопоставить четыре переменные: номер текущего состояния в автомате, текущий символ на ленте, содержимое ленты слева от головки и содержимое ленты справа от головки. Заметим, что машина Тьюринга обращается с двумя половинками ленты как с двумя стеками. При движении головки направо, из правого стека берется верхний элемент и кладется в левый; при движении налево - наоборот, из левого стека верхний элемент кладется в правый. Но так как стеки конечны, а лента бесконечна, то договоримся добавлять в стек символ конца ввода слова <tex>\$</tex>. Тем самым бесконечно пустой хвост ленты виртуально присутствует учтен в стековой машине.