Машина Поста Для уточнения понятия алгоритма амер. математиком Постом (1937 г.) было предложено строгое математическое построение, которое было названо. - презентация

1

2 Машина Поста

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

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

5 Система команд МП Обозначения V i Записать 1 (отметку), перейти к i - той строке программы X i Записать 0 (стереть отметку), перейти к i -той строке i Шаг вправо, перейти к i -той строке i Шаг влево, перейти к i -той строке ? i ; j Если в ячейке 0, то перейти к i -той строке, иначе перейти к j -той строке ! Останов

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

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

8 На ленте проставлена отметка в одной единственной ячейке. Головка стоит слева на некотором расстоянии. Надо стереть отметку и остановить головку слева от ячейки. Пример ? 1 ; 3 3. X ! Программа МП задачи 1

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

10 – программа для машины Поста, приводящая к решению поставленной задачи. Алгоритм (по Посту) Если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.

11 В теории алгоритмов доказано, что машина Поста и машина Тьюринга эквивалентны по своим возможностям несмотря на то, что МП проще, чем МТ.