Машина Тьюринга
Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров1) Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигается головка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемся вычислении используется только конечная часть этой памяти - конечное число ячеек.
Машина Поста
Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Л. Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины эквивалентны и были созданы для уточнения понятия алгоритм.
Принцип работы
МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:
|
|
N. → J |
сдвиг вправо |
|
|
N. ← J |
сдвиг влево |
|
|
N. 1 J |
запись метки |
|
|
N. 0 J |
удаление метки |
|
|
N. ? J1, J0 |
условный переход по метке |
|
|
N. Stop |
останов |
где N. - номер строки, J - строка на которую переходит управление далее.
Для работы машины нужно задать программу и ее начальное состояние (т.е. состояние ленты и позицию каретки). После запуска возможны варианты:
работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
работа может закончиться командой Stop;
работа никогда не закончится.
|
|
1. 0 // cycle P 22. → // renew Q 2. ← 23. 1 3. ? 5,4 24. → 4. Stop 25. ? 26,23 5. → 26. ← 6. ? 7,5 27. 0 7. → 28. ← 8. ? 7,9 29. ? 28,30 9. ← 30. ← 10. 0 // cycle Q 31. ? 1,30 11. ← 12. ? 13,22 13. → 14. ? 15,13 15. → 16. ? 15,17 17. 1 18. ← 19. ? 18,20 20. ← 21. ? 10,20 |
|
Очевидно, что использование в МП нескольких лент и (или) головок позволило бы избежать многочисленных перемещений головки по ленте и перезаписи чисел, существенно упростив программирование, однако эти ограничения на устройство МП никак не ограничивают возможности вычислений в принципе.