Машина Поста Доклад по курсу « Системы Искусственного Интеллекта » Шариповой А. Ф. ИУ 4-93

Понятие « машины Поста » Машина Поста - это не реальная, а мысленная конструкция, которая существует лишь в нашем воображении

Понятие « машины Поста » Состав машины Поста Команды машины Поста Программа машины Поста Представление чисел Постулаты Поста Применение машины Поста

Краткий обзор Машина Поста ( МП ) абстрактная вычислительная машина, которая отличается от машины Тьюринга большей простотой. Обе машины « эквивалентны » и были созданы для уточнения понятия « алгоритм ».

Состав машины Поста Машина Поста ЛентаКаретка

Состав машины Поста. Лента Свойства ленты бесконечная и разделена на секции одинакового размера порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа

Состав машины Поста. Лента в каждой секции ленты может быть : ничего не записано - секция пуста записана метка V - секция отмечена эта информация образует состояние ленты

Состав машины Поста. Каретка Каретка - считывающая и записывающая головка Свойства каретки : распознает стоит или нет метка в распознаваемой секции ставит или стирает метку в той секции, напротив которой она стоит

Состав машины Поста. Работа Суть работы : каретка передвигается вдоль ленты и печатает или стирает метки

Команды машины Поста Команды движения вправо Команды движения влево Команды печатания метки

Команды машины Поста Команды стирания метки Команды передачи управления Команды остановки

Команды машины Поста i – номер команды j – отсылка к команде j1 – отсылка к команде, если метка пуста j2 – отсылка к команде, если метка отмечена i, j, j1, j2 - натуральные числа

Команды машины Поста Примеры команд

Команды машины Поста. Выводы Чтобы Машина Поста начала работать, надо как - то расставить метки по секциям ленты и поставить каретку напротив секции с номером нуль.

Программа машины Поста Свойства программы : На первом месте – команда с номером 1 На k- м месте – команда с номером k Для каждой отсылки каждой команды списка найдется в списке такая команда, номер которой равен рассматриваемой отсылке

Программа машины Поста Пример программы :

Программа машины Поста Не верные программы : не выполняется первое свойство

Программа машины Поста Не верные программы : не выполняется второе свойство

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

Программа машины Поста Возможное завершение программы : положение каретки до команды следующая командазавершение программы безрезультативная остановка результативная остановка

Программа машины Поста. Пример Начальное состояние ленты : Программа :

Программа машины Поста командаположение кареткиописание команды Поставить метку Перевести каретку на клетку вправо Распознавание клетки. В клетке нет метки, значит следующей командой будет команда 4. Перевести каретку на клетку вправо

Программа машины Поста командаположение кареткиописание команды Распознавание клетки. В клетке есть метка, значит следующей командой будет команда 3. Перевести каретку на клетку вправо Стирание метки – невозможная команда безрезультативная остановка

Представление чисел Массив – конечная последовательность идущих подряд друг за друг отмеченных секций ленты, заключенных между двумя пустыми секциями. Количество отмеченных таким образом секций – длина массива.

Представление чисел Число n записывается на ленте массивом длины (n+1). Пример представления чисел 4, 0, 1:

Представление чисел Пример. Прибавление к единственному числу, записанному на ленте, единицы. В начальном состоянии каретка стоит напротив любой метки

Представление чисел

Постулаты Поста 1936 год статья « Финитные комбинаторные процессы – формулировка 1», « рабочая гипотеза »: 1. из разрешимости задачи, при помощи машины Поста, следует разрешимость при помощи алгоритма. 2. из разрешимости задачи, при помощи алгоритма, следует разрешимость при помощи машины Поста.

Применение машины Поста Для лучшего понимания термина « алгоритм » Для понимания принципов работы ЭВМ, в связи с наличием общих свойств : наличие атомарных носителей информации, наличие некоторого набора элементарных действий, работа на основе особой инструкции – программы.