'

Машина Поста

Понравилась презентация – покажи это...





Слайд 0

Машина Поста


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


×

HTML:





Ссылка: