Компьютерная презентация на тему "Машина Поста"
Машина Поста – это несуществующая реально вычислительная машина, созданная для уточнения (формализации) понятия алгоритма.Представляет собой универсальный исполнитель, позвроляющий ввводить начальные данные и читать результат выполнения программы.
Скачать:
| Вложение | Размер |
|---|---|
 mashina_posta.pptx | 139.2 КБ |
Предварительный просмотр:
Подписи к слайдам:
Машина Поста – это абстрактная вычислительная машина, созданная для уточнения понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
История создания В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой.
Устройство машины
Принцип действия Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Кареткой управляет программа, состоящая из строк команд.
Каждая команда имеет следующий синтаксис: i K j, где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд: V j - поставить метку, перейти к j-й строке программы. X j - стереть метку, перейти к j-й строке программы. <- j - сдвинуться влево, перейти к j-й строке программы. -> j - сдвинуться вправо, перейти к j-й строке программы. ? j 1 ; j 2 - если в ячейке нет метки, то перейти к j 1 -й строке программы, иначе перейти к j 2 -й строке программы. ! – конец программы (стоп ).
Варианты окончания выполнения программы: Команда «стоп»; Выполнение недопустимой команды; Уход в бесконечность, зацикливание.
Программой машины Поста будем называть конечный список команд машины Поста, обладающий следующими двумя свойствами : На первом месте в этом списке стоит команда с номером 1, на втором месте - команда с номером 2 и т.д .; Отсылка любой из команд списка совпадает с номером некоторой команды списка.
Пример работы машины Поста: Задача: увеличить число 3 на единицу. Решение: 1 . -> 2 2 . ? 1;3 3 . <- 4 4 . V 5 5 . !
Применение машины Поста Для лучшего понимания термина «алгоритм»; Для понимания принципов работы ЭВМ.
Дополнительные источники информации: Википедия: https :// ru.wikipedia Интернет-ресурс «Планета информатики» : http :// www.inf1.info/machinepost .
Браво, Феликс!
О падающих телах. Что падает быстрее: монетка или кусочек бумаги?
Астрономический календарь. Ноябрь, 2018
Северное сияние
Девочка-Снегурочка