Стековые машины, эквивалентность двухстековой машины МТ — различия между версиями
(Новая страница: «== Стековая машина == <font face="Times" size="3"> Файл:StackMachine.png * Каждой конфигурации машины Тьюринга…») |
(→Стековая машина) |
||
| Строка 3: | Строка 3: | ||
[[Файл:StackMachine.png]] | [[Файл:StackMachine.png]] | ||
| − | * Каждой конфигурации машины Тьюринга можно сопоставить четыре переменные: номер текущего состояния в автомате, текущий символ на ленте, содержимое ленты слева от головки и содержимое ленты справа от головки. Заметим, что машина Тьюринга обращается с двумя половинками ленты как с двумя стеками. При движении головки направо, из правого стека берется верхний элемент и кладется в левый; при движении налево - наоборот, из левого стека верхний элемент кладется в правый. Но так как стеки конечны, а лента бесконечна, то договоримся добавлять в стек символ конца ввода слова <tex>\$</tex>. Тем самым бесконечно пустой хвост ленты | + | * Каждой конфигурации машины Тьюринга можно сопоставить четыре переменные: номер текущего состояния в автомате, текущий символ на ленте, содержимое ленты слева от головки и содержимое ленты справа от головки. Заметим, что машина Тьюринга обращается с двумя половинками ленты как с двумя стеками. При движении головки направо, из правого стека берется верхний элемент и кладется в левый; при движении налево - наоборот, из левого стека верхний элемент кладется в правый. Но так как стеки конечны, а лента бесконечна, то договоримся добавлять в стек символ конца ввода слова <tex>\$</tex>. Тем самым бесконечно пустой хвост ленты учтен в стековой машине. |
* Если слово допускается в машине Тьюринга <tex>\Rightarrow</tex> оно допускается и в стековой машине. | * Если слово допускается в машине Тьюринга <tex>\Rightarrow</tex> оно допускается и в стековой машине. | ||
Версия 13:24, 23 декабря 2010
Стековая машина
- Каждой конфигурации машины Тьюринга можно сопоставить четыре переменные: номер текущего состояния в автомате, текущий символ на ленте, содержимое ленты слева от головки и содержимое ленты справа от головки. Заметим, что машина Тьюринга обращается с двумя половинками ленты как с двумя стеками. При движении головки направо, из правого стека берется верхний элемент и кладется в левый; при движении налево - наоборот, из левого стека верхний элемент кладется в правый. Но так как стеки конечны, а лента бесконечна, то договоримся добавлять в стек символ конца ввода слова . Тем самым бесконечно пустой хвост ленты учтен в стековой машине.
- Если слово допускается в машине Тьюринга оно допускается и в стековой машине.
Литература
- Н.К.Верещагин, А.Шень - "Вычислимые функции"
