Стековые машины, эквивалентность двухстековой машины МТ

Материал из Викиконспекты
Версия от 21:58, 16 декабря 2010; 192.168.0.2 (обсуждение) (Новая страница: «== Стековая машина == <font face="Times" size="3"> Файл:StackMachine.png * Каждой конфигурации машины Тьюринга…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Стековая машина

StackMachine.png

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

Литература

  • Н.К.Верещагин, А.Шень - "Вычислимые функции"