Операции над МТ Алгоритмическая машина Поста

Операции над МТ

Алгоритмическая машина Поста

• (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм»
• Абстрактная машина Поста состоит
• из бесконечной ленты, разделенной на равные секции,
• считывающе-записывающей головки.
• Каждая секция может быть либо пуста (т.е. в нее ничего не записано), либо заполнена (отмечена – т.е. в нее записана метка).
• Состояние ленты и информация о положении головки характеризуют состояние машины Поста.