Машина Поста. Уточнение понятия Алгоритма

Размещено на http://www.allbest.ru/

Реферат

по дисциплине: Архитектура ЭВМ

на тему: Машина Поста. Уточнение понятия Алгоритма

Выполнил:

Удодов Иван Сергеевич

2013 год

Эмиль Леон Пост (1897-1954) - американский математик и логик. Один из основателей многозначной логики (1921).

Трудился в области математической логики:

- создал алгебру Поста, классы Поста функций алгебры логики;

- предложил абстрактную вычислительную машину - машину Поста.

Одним из центральных понятий информатики является понятие алгоритма. Практически одновременно с Тьюрингом (тоже в 1936 году) и независимо от него, американский математик Эмиль Пост предлагает еще более простого исполнителя, названного позже машиной Поста. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Машина Поста - это абстрактная (т. е., не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать - в известном смысле - любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию. Разработка программ для машин Поста - достаточно эффективный этап в обучении алгоритмизации, т. к., в процессе написания этих программ учащиеся учатся разбивать интуитивно понятные вычислительные процедуры на элементарные действия. Изучение машины Поста полезно как школьникам, интересующимся информатикой и математикой, так и студентам младших курсов, обучающимся по специальности “прикладная математика и информатика”. При этом теоретический материал доступен даже школьникам младших классов, но требует в этом случае некоторых методических поправок. Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) - программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие “всякий алгоритм”, а с другой стороны - точное понятие “машина Поста”. Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера - ячейки.

Рис. 1. - В каждый момент времени каретка указывает на одну из ячеек:

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V.

Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ячейкам.

Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие - “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

Действия каретки подчинены программе, состоящей из перенумерованного набора команд (команды можно представлять как строки программы). Команды бывают шести типов:

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

1. попытка записать 1 (метку) в заполненную ячейку;

2. попытка стереть метку в пустой ячейке;

3. бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий - зацикливание - ничуть не лучше вышеперечисленного).

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

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

Условимся каждый шаг программы обозначать номером. Команды машины будем обозначать следующим образом:

Таблица 1:

Будем говорить, что мы можем применить программу к текущему состоянию машины Поста.

Если выполнение программы не приведет к зацикливанию, т. е., рано или поздно мы выполним команду останов.

Пример программы, которая не применима ни к одному состоянию машины Поста:

Рис. 2:

Существует также Тренажер «Машина Поста».

Тренажёр «Машина Поста» - это учебная модель универсального исполнителя (абстрактной вычислительной машины), основанного на работах Э.Л. Поста по уточнению понятия алгоритма.

Таблица 2:

Рассмотрим задания для машины Поста и их решения.

Задание 1:

На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки.

Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

Решение:

Сначала попробуем описать алгоритм обычным языком.

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

- сделать шаг вправо;

- проверить, заполнена ли ячейка;

- если она пустая, то повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку.

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

Рис. 3. - Программа для машины Поста:

Задание 2:

Увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).

Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число.

Это связано с тем, что одна метка обозначает ноль, а уже две - единицу, и т. д.

Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:

Рис. 4:

А процесс выполнения может быть таким:

Рис. 5:

Задание 3:

На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

Решение представлено на рисунке 6.

Рис. 6:

Задание 4: вычислительный запрограммированный алгоритм

На ленте машины Поста расположен массив из 2-1 меток. Составить программу удаления средней метки массива.

Решение:

Идея решения состоит в следующем: во вторых ячейках от каждого края массива ставим “маячки-пузырьки” (эти ячейки делаем пустыми). Далее последовательно перемещаем к центру левый и правый пузырьки. Эти пузырьки встретятся ровно на центральном элементе исходного массива. При реализации программы надо отдельно учесть три случая:

n = 1;

n = 3;

n > 3.

Считаем, что в начале работы каретка стоит на самой левой метке массива.

Рис. 7:

Размещено на Allbest.ru