Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

Энциклопедичный YouTube

  • 1/3
    Просмотров:
    12 808
    1 376
    1 135
  • Информатика. Машина Поста.
  • Машина Поста. Автоматическая обработка информации.
  • Лекція 4. Машина Поста. Поняття машини Поста. Розв'язання задач

Субтитры

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

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

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

i. K j

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

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

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

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

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

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

Пример

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

         ⇓
…0010010010110…
   ╚═══╝ ╚═╝
     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-й строке возможно зацикливание, если .

Литература

Эта страница в последний раз была отредактирована 24 марта 2022 в 10:38.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).