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