Машина Поста

Слайд 2

Для уточнения понятия алгоритма амер. математиком Постом (1937 г.) было предложено строгое

Для уточнения понятия алгоритма амер. математиком Постом (1937 г.) было предложено строгое
математическое построение, которое было названо «машиной», т. к. в нем используются некоторые понятия реальных машин – память, команда и др.

Слайд 3

– бесконечная лента, в ячейках которой можно записывать всего два знака: 1

– бесконечная лента, в ячейках которой можно записывать всего два знака: 1
(ставить метку) или 0 (стирать метку) и головка для чтения/записи, управляемая программой.

Машина Поста (МП)

Слайд 4

Система команд МП

Система команд МП

Слайд 5

Недопустимые действия МП

Попытка записать 1 (отметку) в заполненную ячейку
Попытка стереть

Недопустимые действия МП Попытка записать 1 (отметку) в заполненную ячейку Попытка стереть
отметку в пустой ячейке
Уход головки в бесконечность или зацикливание

Слайд 6

состоит из пронумерованных строк, в каждой строке записывается только одна команда.

Программа МП

состоит из пронумерованных строк, в каждой строке записывается только одна команда. Программа МП

Слайд 7

На ленте проставлена отметка в одной единственной ячейке.
Головка стоит слева на

На ленте проставлена отметка в одной единственной ячейке. Головка стоит слева на
некотором расстоянии. Надо стереть отметку и остановить головку слева от ячейки.

Пример

→ 2
? 1 ; 3
X 4
← 5
!

Программа МП задачи

Слайд 8

– всякий алгоритм представим в форме машины Поста.

Тезис Поста

– всякий алгоритм представим в форме машины Поста. Тезис Поста

Слайд 9

– программа для машины Поста, приводящая к решению поставленной задачи.

Алгоритм (по Посту)

Если

– программа для машины Поста, приводящая к решению поставленной задачи. Алгоритм (по
для решения задачи можно построить машину Поста, то она алгоритмически разрешима.
Имя файла: Машина-Поста.pptx
Количество просмотров: 706
Количество скачиваний: 16