AAA
Обычный Черный

Кто не делится найденным, подобен свету в дупле секвойи (древняя индейская пословица)

версия для печатиВерсия для печати



Библиографическая запись: Машина Поста-Успенского. — Текст : электронный // Myfilology.ru – информационный филологический ресурс : [сайт]. – URL: https://myfilology.ru//165/informaczionnye-texnologii/mashina-posta-uspenskogo/ (дата обращения: 28.03.2024)

Машина Поста-Успенского

Машина Поста-Успенского

Содержание

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

    Элементы машины и их характеристики

    Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера. Порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Поэтому естественно ввести на ленте «целочисленную систему координат», занумеровав секции целыми числами ..., —3, —2, —1,0, 1, 2, 3, ... . Будем считать, что система координат жестко сопоставлена с лентой, и получим таким образом возможность указывать какую-либо секцию ленты, называя ее порядковый номер, или координату.

    В каждой секции ленты может быть либо ничего не записано (такая секция называется пустой), либо записана метка V (тогда секция называется отмеченной). Информация о том, какие секции пусты, а какие отмечены, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ее секциям1). Состояние ленты меняется в процессе работы машины.

    Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию, или держит ее в поле зрения. Информация о том, какие секции пусты, а какие отмечены и где стоит каретка, образует состояние машины Поста. Таким образом, состояние машины слагается из состояния ленты и указания номера той секции, которую обозревает каретка. За единицу времени (шаг) каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может поставить (напечатать) или уничтожить (стереть) метку в той секции, против которой она стоит, а также распознать, стоит или нет метка в обозреваемой ею секции.

    Функционирование машины Поста

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

    Каждая программа машины Поста состоит из команд. Командой машины Поста будем называть выражение, имеющее один из следующих шести видов (буквы i, j, j1, j2 означают всюду натуральные числа 1, 2, 3, 4, 5, ... ):

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

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

    Программа является той инструкцией, на основании которой работает машина. Работа машины на основании заданной программы (и при заданном начальном состоянии) происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы (что значит «выполнить команду», будет объяснено ниже). Эта команда выполняется за один шаг, после чего машина приступает к выполнению той команды, номер которой (назовем его ∝) равен отсылке (одной из отсылок, если их две) первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение команды, номер которой равен отсылке команды с номером ∝. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-м шаге выполнялась команда с номером i, тогда, если эта команда имеет единственную отсылку j, то на k + 1-м шаге выполняется команда с номером /; если эта команда имеет две отсылки j1 и j2, то на k + 1-м шаге выполняется одна из двух команд — с номером j1 или с номером j2; если, наконец, выполняющаяся на k-м шаге команда вовсе не имеет отсылки, то на  k + 1-м шаге и на всех последующих шагах не выполняется никакая команда: машина останавливается. Осталось объяснить, что значит выполнить команду и какая из отсылок — при наличии двух — выбирается в качестве номера следующей команды.

    Выполнение команды движения вправо состоит в том, что каретка сдвигается на одну секцию вправо. Выполнение команды движения влево состоит в том, что каретка сдвигается на одну секцию влево. Выполнение команды печатания метки состоит в том, что каретка ставит метку на обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая перед началом выполнения команды секция пуста; если же на обозреваемой секции уже стоит метка, команда считается невыполнимой. Выполнение команды стирания метки состоит в том, что каретка уничтожает метку в обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая секция отмечена; если же на обозреваемой секции и так нет метки, команда считается невыполнимой. Выполнение команды передачи управления с верхней отсылкой j1 и нижней отсылкой j2 никак не изменяет состояния машины: ни одна из меток не уничтожается и не ставится, и каретка также остается неподвижной (машина делает, так сказать, «шаг на месте»); однако если секция, обозреваемая перед началом выполнения этой команды, была пуста, то следующей должна выполняться команда с номером j1, если же эта секция была отмечена, следующей должна выполняться команда с номером j2 (роль команды передачи управления сводится, следовательно, к тому, что каретка во время выполнения этой команды как бы «распознает», стоит ли перед ней метка). Выполнение команды остановки тоже никак не меняет состояния машины и состоит в том, что машина останавливается.

    Основные отличия машины Поста-Успенского от компьютера

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

    2. В случае машины Поста мы ничего не говорили о том, как именно обеспечивается выполнение программы. Можно мыслить себе, например, что рядом с машиной Поста стоит человек, читает написанную на бумаге программу и, следуя ей, передвигает каретку, печатает и стирает метку. Существенно подчеркнуть, что в ЭВМ выполнение программы происходит автоматически. Программа для ЭВМ закодирована специальным образом и записывается так, чтобы она была доступна для «восприятия» машины. Часто такой доступной машине формой записи является запись в виде системы дырок, пробиваемых на ленте (перфоленте) или карточках (перфокартах). После того как изготовлена перфолента (или перфокарты) с программой, работа ЭВМ происходит под управлением этой перфоленты (или этих перфокарт) без дальнейшего вмешательства человека. (Разумеется, нетрудно создать устройство, обеспечивающее автоматическую, без участия человека, работу машины Поста.) В первом приближении работу ЭВМ можно сравнить с работой механического фортепьяно, в котором последовательность нажатия клавиш точно определена записанной на перфоленте «программой» и осуществляется без участия человека. 

    3. Наиболее существенное, принципиальное отличие ЭВМ от машины Поста состоит в следующем. В запоминающее устройство — на ленту машины Поста — перед началом работы записывается исходное данное (например, кортеж чисел, подлежащих сложению). Программа, которая должна применяться к этому исходному данному и согласно которой работает машина, находится как бы в стороне. В ЭВМ перед началом работы машины программа закладывается в запоминающее устройство вместе с исходным данным. (В этом, кстати, еще одно отличие ЭВМ от механического фортепьяно: в механическом фортепьяно записанная на перфоленте программа «читается» специальным устройством, и по мере чтения происходит игра; это устройство выполняет, таким образом, роль пианиста, играющего по разложенным перед ним нотам. В ЭВМ перфолента с записанными на ней программой и исходным данным перед началом работы машины обрабатывается специальным «устройством ввода», которое прочитывает содержащуюся на перфо80 ленте информацию и помещает ее в запоминающее устройство; в этом отношении машина подобна пианисту, который сперва выучивает ноты наощупь, а потом играет уже по памяти, не глядя в ноты.) Содержание запоминающего устройства в машине в некоторый момент — перед началом работы — будем называть начальной информацией. В машине Поста начальная информация состоит только из исходного данного. В ЭВМ начальная информация состоит из исходного данного и программы. Важно подчеркнуть, что разделение начальной информации в ЭВМ на исходное данное и программу довольно условно. Вся эта информация, включая и ту ее часть, которая названа «программой», может подвергаться различным преобразованиям в процессе работы машины. Эта возможность изменять сами команды в процессе работы, отсутствующая в машине Поста, является очень важной чертой современных ЭВМ. С другой стороны, содержание более или менее любого участка запоминающего устройства очень часто можно интерпретировать как команду. Поэтому разделение информации, содержащейся в запоминающем устройстве, на программу и исходное данное вообще имеет смысл только в начальный момент, затем на каждом шаге вся эта информация в целом подвергается переработке. Естествен вопрос: по какому же закону происходит переработка информации, содержащейся в запоминающем устройстве? Эта переработка происходит в свою очередь на основе некоторого правила, которое мы будем называть Универсальной Программой. Универсальную Программу ни в коем случае нельзя смешивать с частной программой, предназначенной для решения той или иной конкретной задачи и применяющейся к исходным данным. Частная программа зависит от решаемой задачи, в то время как Универсальная Программа одна для всех задач; в существующих ЭВМ она заложена в самой конструкции машины (поэтому такие машины часто называют универсальными). Подытожим сказанное. В машине Поста вначале в запоминающее устройство закладывается исходное данное, после чего работа происходит по программе, не находящейся в запоминающем устройстве. В ЭВМ вначале в запоминающее устройство закладывается начальная информация, слагающаяся из частной программы решения данной задачи и исходного данного, после чего работа (а именно, переработка всего содержания запоминающего устройства) происходит по Универсальной Программе, воплощенной в конструкции машины/

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

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


    Успенский В. А. Машина Поста / Гл. ред. физ.-мат. лит.. — 2-е изд., испр.. — М.: Наука, 1988. — 96 с. 

    10.07.2022, 692 просмотра.


    Уважаемые посетители! С болью в сердце сообщаем вам, что этот сайт собирает метаданные пользователя (cookie, данные об IP-адресе и местоположении), что жизненно необходимо для функционирования сайта и поддержания его жизнедеятельности.

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

    Dear visitors! It is a pain in our heart to inform you that this site collects user metadata (cookies, IP address and location data), which is vital for the operation of the site and the maintenance of its life.

    If you do not want to provide this data for processing under any pretext, please leave the site immediately and we will not tell anyone that you were here. With the same care, the site administration.