Ср. Июн 5th, 2024

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

Абстрактная машина Поста состоит из нескончаемой ленты, разбитой на равные секции, также считывающей-записывающей головки. Любая секция может быть или пуста (т.е. в нее ничего не записано), или заполнена (отмечена — т.е. в нее записана метка). Вводится понятие состояние ленты как информация о том, какие секции пусты, а какие отмечены (по-другому: состояние ленты — это рассредотачивание меток по секциям, т.е. это функция, которая каждому числовому номеру секции ставит в соответствие или метку, или символ «пусто»). Естественно, в процессе работы машины состояние ленты изменяется. Состояние ленты и информация о положении головки охарактеризовывают состояние машины Поста.

Условимся обозначать головку знаком «Ñ» над обозреваемой секцией, а метку — знаком «М» снутри секции. Пустая секция никакого знака не содержит. За один такт (его именуют шагом) головка может двинуться на одну секцию на право либо на лево и поставить либо удалить метку. Работа машины Поста заключает в переходе от 1-го состояния машины к другому в согласовании с данной программкой, которая строится из отдельных команд. Любая команда имеет последующую структуру: хКу, где х — номер исполняемой команды; К — указание о выполняемом действии; у — номер последующей команды (наследника). Система команд машины включающая 6 действий, представлена в табл. 7.1.

Таблица 7.1.

Данный список должен быть дополнен последующими критериями:

  • команда <хМу> может быть выполнена исключительно в пустой секции;
  • команда <хСу> может применяться только к заполненной секции;
  • номер наследника хоть какой команды (у) должен соответствовать номеру команды, неотклонимой имеющейся в данной программке.

Если данные условия не производятся, происходит безрезультативная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде <х стоп> является действенной, т.е. она происходит после того, как итог деяния метода получен. Не считая того, вероятна ситуация, когда машина не останавливается никогда — это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки либо программка не перебегает к этой команде.

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

Целое число k записывается на ленте машины Поста средством k + 1 последующих попорядку отмеченных секций, т.е. применяется унарная система счисления (см. п. 4.1). Примыкающие записи чисел на ленте делятся одной либо несколькими пустыми секциями. Ниже приведен пример записи чисел 0, 2 и 3.

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

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock