Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет.

Презентация:



Advertisements
Похожие презентации
«ОБРАБОТКА ИНФОРМАЦИИ ИАЛГОРИТМЫ». Результаты Правила обработки Исполнитель Исходные данные.
Advertisements

Говорят, что формальный исполнитель А имитирует другого формального исполнителя В, если: каждому объекту, которым управляет исполнитель В, однозначно.
Машина Поста Для уточнения понятия алгоритма амер. математиком Постом (1937 г.) было предложено строгое математическое построение, которое было названо.
Машина Поста Доклад по курсу « Системы Искусственного Интеллекта » Шариповой А. Ф. ИУ 4-93.
Автоматическая обработка информации Чебышев Михаил10 класс.
Автоматическая обработка информации. В 30-х годах XX века возникает новая наука теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой.
Машина Тьюринга Для формального определения алгоритма математиками Тьюрингом (1936 г.) и независимо от него Постом (1937 г.) были предложены абстрактные.
СИСТЕМА КОМАНД МАШИНЫ ПОСТА ПЕРЕМЕЩЕНИЕ КАРЕТКИ РАБОТА С МЕТКАМИ ЦИКЛЫ.
Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный.
Авторы: ученики 10-В класса СОШ269 ЗАТО Снежногорск. Руководитель Татаришвили Л. И. МАШИНА ПОСТА.
Автоматическая обработка информации 10 класс. Модель машины Поста Программа – алгоритм, записанный по строгим правилам языка команд исполнителя – на языке.
Лекция Машина Тьюринга. Типы алгоритмов. История создания Интенсивный поиск универсального уточнения алгоритма предложил примерно 20 формальных конструкций.
Начала программирования Занятие 2. Машина Поста. Умный мячик.
LOGO Определение машины Тьюринга. Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс Это математический объект, а не физическая.
Элементы теории алгоритмов Фестиваль педагогических идей «Открытый урок» уч.г. festival.1september.ru Narzyaeva I.Y., 2010.
Ребята, сегодня вы познакомитесь с «игрушечной» машиной, которой в реальной жизни нет, но ее можно построить. Изобрел эту машину более 70-ти лет назад.
Обработка информации и алгоритмы Алгоритмическая машина Поста.
Обработка информации Исполнитель Исходные данные Правила обработки Результаты Модель обработки информации.
Алгоритм - способ выполнения арифметических действий над десятичными числами. Обозначение любой последовательности действий, приводящей к решению поставленной.
Кафедра ЮНЕСКО по НИТ1 Формализация понятия «Алгоритм» Информатика.
Транксрипт:

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

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

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: i K j, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд: V j - поставить метку, перейти к j-й строке программы. X j - стереть метку, перейти к j-й строке программы. j - сдвинуться вправо, перейти к j-й строке программы. ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы. ! – конец программы (стоп). У команды «стоп» отсылки нет.

Варианты окончания выполнения программы на машине Поста: Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми). Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).