52. Машина Поста

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

Принцип работы 

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

i K j,

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

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

1. V j - поставить метку, перейти к j-й строке программы.

2. X j - стереть метку, перейти к j-й строке программы.

3. <- j - сдвинуться влево, перейти к j-й строке программы.

   1. j - сдвинуться вправо, перейти к j-й строке программы.

4. ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

5. ! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

• работа может закончиться командой Stop;

• работа никогда не закончится.

53. Понятие нормального алгоритма

Норма́льный алгори́тм Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ —машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.

Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.

54. Алфавит и схема алгоритма.

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

Определение всякого нормального алгоритма состоит из двух частей: определения алфавита алгоритма (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида  , где   и   — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида  , где   и   — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы   и   не принадлежат алфавиту алгоритма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Примером схемы нормального алгоритма в пятибуквенном алфавите   может служить схема

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

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

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгоритму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть «принципом нормализации».

Нормальные алгоритмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгоритма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.