Машина Тьюринга. Машина Поста
Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров1) Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигается головка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемся вычислении используется только конечная часть этой памяти - конечное число ячеек.
Машина Поста
Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Л. Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины эквивалентны и были созданы для уточнения понятия алгоритм.
Принцип работы
МП состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой - 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа строк. Всего команд шесть:
|
|
|
Дата добавления: 2016-01-06; просмотров: 13; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!