Машина поста умножение двух чисел

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

Принцип работы [ править | править код ]

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

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

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

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

  • V j — поставить метку, перейти к j -й строке программы;
  • X j — стереть метку, перейти к j -й строке;
  • ← j — сдвинуться влево, перейти к j -й строке;
  • → j — сдвинуться вправо, перейти к j -й строке;
  • ? j1; j2 — если в ячейке нет метки, то перейти к j1 -й строке программы, иначе перейти к j2 -й строке;
  • ! — конец программы («стоп», останов).
Читайте также:  Windows 7 домашняя расширенная sp1 x64

В команде «стоп» переход на следующую строку не указывается.

После программы запуска возможны варианты:

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

Пример [ править | править код ]

Для сложения и вычитания натуральных (целых неотрицательных) чисел P и Q их можно представить на ленте набором из P единиц и Q , отделённых друг от друга одним нулём; пусть исходное положение каретки находится на крайней левой «1» группы единиц Q (помечено символом « ⇓ »):

⇓ …00111110111000… ╚═══╝ ╚═╝ P Q

Сложение двух чисел тривиально — достаточно поставить « 1 » между числами и стереть одно крайнее правое « 1 » у представления Q .

Программа вычитания таких чисел состоит из последовательного изменения крайних левых « 1 » у представления Q и правых « 1 » у представления P . В начале программы каретка установлена на крайнюю левую «1» у Q :

1. ← — шаг влево 2. ? 1; 3 — если в ячейке пусто, перейти к 1 -шагу, если нет — к 3 3. X — удалить метку 4. → — шаг вправо 5. ? 4; 6 — если в ячейке пусто, перейти к 4 -шагу, если нет — к 6 6. X — удалить метку 7. → — шаг вправо 8. ? 9; 1 — если в ячейке пусто, перейти к 9 шагу, если нет — к 1 9. ! — конец

В 5-й строке возможно зацикливание, если P>"> Q > P <displaystyle Q>P> P>"/> .

Reshak.ru — сборник решебников для учеников старших классов. Здесь можно найти решебники, ГДЗ, переводы текстов по школьной программе. Практически весь материал, собранный на сайте — сделанный для людей. Все решебники выполнены качественно, с приятной навигацией. Вы сможете скачать гдз, решебник английского, улучшить ваши школьные оценки, повысить знания, получить намного больше свободного времени.

Читайте также:  Как восстановить иконку контакты на андроиде

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

Информация

© adminreshak.ru

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

Пример

Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):

Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

Читайте также:  Программа для отслеживания изменений на сайте

Проверить корректность алгоритма можно в уме, на листочке, либо с помощью этой программы.

Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.

Если вас заинтересовала тема, предлагаю подумать над следующими задачами:

  • Вывод i-го числа Фибоначчи
  • Деление двух натуральных чисел c остатком
  • «Сборщик мусора». На ленте неизвестным образом распределено конечное количество (n) отмеченных ячеек. Необходимо «сгрести» их в одну кучу, т. е. машина должна оставить на ленте только блок в n отметок подряд.

P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.

Оцените статью
Добавить комментарий

Adblock
detector