Машина поста сообщение кратко
Обновлено: 25.06.2024
Система команд машины, включающая шесть действий
Данный перечень должен быть дополнен следующими условиями:
- Команда может быть выполнена только в пустой секции;
- Команда может применяться только к заполненной секции;
- Номер наследника любой команды (у) должен соответствовать номеру команды, обязательной имеющейся в данной программе.
Если данные условия не выполняются, происходит безрезультатная остановка машины, т.е. остановка до получения запланированного результата. В отличие от этой ситуации, остановка по команде является результативной, т.е. она происходит после того, как результат действия алгоритма получен. Кроме того, возможна ситуация, когда машина не останавливается никогда - это происходит, если ни одна из команд не содержит в качестве последователя номера команды остановки или программа не переходит к этой команде.
Еще одним исходным соображением является следующее: поскольку знаки любого конечного алфавита могут быть закодированы цифрами, преобразование исходного слова может быть представлено в виде некоторых правил обработки чисел. По этой причине в машине Поста предусматривается только запись (представление) целых положительных чисел.
Целое число k записывается на ленте машины Поста посредством k + 1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления. Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями. Ниже приведен пример записи чисел 0, 2 и 3.
Рис. 2.2. Пример записи чисел 0, 2 и 3
Круг вычислительных задач, решаемых с помощью машины Поста, весьма широк. Однако как указывалось выше, на уровне элементарных шагов все сводится к постановке или удалению метки и сдвигу головки. В качестве примеров рассмотрим несколько задач, традиционно обсуждаемых при освоении машины Поста. Поскольку вид программы (последовательности команд машины) зависит от начального состояния машины, оно должно быть в явном виде указано в постановке задачи.
На ленте записано некоторое число, и головка обозревает одну из помеченных секций (любую). Составить программу прибавления единицы к этому числу. Ситуация иллюстрируется рисунком 2.3.
Рис. 2.3. Иллюстрация рассматриваемой ситуации
Программа, обеспечивающая решение задачи, состоит из 4-х команд:
Рис. 2.4. Программа
Последовательное исполнение команд 1 и 2 приводит к тому, что головка за два такта работы машины сдвигается на одну позицию вправо. Это передвижение продолжается до тех пор, пока после очередного сдвига под головкой не окажется пустой ячейки - тогда по команде 3 в нее будет поставлена метка и по команде 4 машина остановится.
На ленте записано некоторое число, и головка обозревает одну из свободных секций (любую) левее записи. Составить программу прибавления единицы к этому числу.
Рис. 2.5. Программа
Комментарий к работе программы подобен приведенному выше с той лишь разницей, что метка ставится перед исходным числом.
Можно показать (это предлагается сделать в контрольных заданиях к данному разделу), что с помощью машины Поста реализуются (хотя и довольно громоздко) все арифметические действия над числами в унарной системе счисления*. Числа же, как было показано ранее, могут быть использованы для кодирования любой дискретной информации. В частности, состояние ленты можно представить словом в двоичном алфавите, где 0 будет соответствовать пустой секции, а 1 - отмеченной. В процессе работы меняется состояние ленты и, следовательно, от исходного слова происходит переход к выходному, представленному в том же двоичном алфавите.
* Машина Поста обеспечивает весьма неплохую и полезную практику программирования. Недостатком оказывается чисто теоретический (т.е. непроверяемый) характер программ, однако он достаточно легко преодолевается, если построить эмуляцию машины на каком-либо языке программирования.
16 декабря 2020 mob25
На этом шаге мы рассмотрим машину Поста.
Рис.1. Состояние машины Поста
Команда машины Поста имеет следующую структуру:
где n - порядковый номер команды, K - действие, выполняемое головкой, m - номер следующей команды, подлежащей выполнению.
Существует всего шесть команд машины Поста, рис.2.
Рис.2. Команды машины Поста
Ситуации, в которых головка должна наносить метку там, где она уже имеется, или, наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми).
Программой для машины Поста будем называть непустой список команд, такой что:
- на n-м месте команда с номером n;
- номер каждой команды совпадает с номером какой-либо команды списка.
С точки зрения свойств алгоритмов, изучаемых с помощью машины Поста, наибольший интерес представляют причины останова машины при выполнении программы:
- останов по команде "стоп". Такой останов называется результативным и указывает на корректность алгоритма (программы);
- останов при выполнении недопустимой команды. В этом случае останов называется безрезультативным;
- машина не останавливается никогда. В этом и в предыдущем случае мы имеем дело с некорректным алгоритмом (программой).
Будем понимать под начальным состояние головки ее положение против пустой клетки левее самой левой метки на ленте.
Рассмотрим реализацию некоторых типичных элементов программ машины Поста.
Рис.3. Пример фрагмента программы машины Поста
1. Пусть задано исходное состояние головки и требуется на пустой ленте написать две метки: одну в секцию под головкой, вторую справа от нее. Это можно сделать по следующей программе (справа от команды показан результат ее выполнения, рис.3).
2. Покажем, как можно воспользоваться командой условного перехода для организации циклического процесса. Пусть на ленте имеется запись из нескольких меток подряд и головка находится над самой крайней меткой справа. Требуется перевести головку влево до первой пустой позиции.
Программа будет иметь следующий вид:
Рис.4. Программа машины Поста
Команда условного перехода является одним из основных средств организации циклических процессов, например, для нахождения первой метки справа (или слева) от головки, расположенной над пустой клеткой; нахождение слева (или справа) от головки пустой клетки, если она расположена над меткой и т.д.
3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними.
Рис.5. Запись чисел 3 и 5 на ленте машины Поста
Обратим внимание, что используемая в машине Поста система записи чисел является непозиционной.
Составим программу для прибавления к произвольному числу единицы. Предположим, что на ленте записано только одно число и головка находится над одной из клеток, в которой находится метка, принадлежащая этому числу:
Рис.6. Увеличение числа на единицу
Для решения задачи можно переместить головку влево (или вправо) до первой пустой клетки, а затем нанести метку.
Программа, добавляющая к числу метку справа, имеет вид:
Рис.7. Текст программы, добавляющей метку справа
Программа, добавляющая к числу метку слева, имеет вид:
Рис.8. Текст программы, добавляющей метку слева
Отличие только в направлении движения головки в первой команде. Проверьте работоспособность этих программ на каких-либо частных примерах.
Предположим, что головка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавить единицу. В этом случае программа усложняется. Появится "блок поиска числа" - две команды, приводящие головку в состояние, рассмотренное в предыдущем примере:
Рис.9. Блок поиска числа
Ниже - полные тексты программ, добавляющие единицу слева и справа соответственно:
Рис.10. Тексты программ
В первом случае не нужно перемещать головку к крайней левой метке числа.
Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:
- неделимые носители информации (клетки - биты), которые могут быть заполненными или незаполненными;
- ограниченный набор элементарных действий - команд, каждая из которых выполняется за один такт (шаг).
Обе машины работают на основе программы. Однако в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста, и т.д.
На следующем шаге мы рассмотрим машину Тьюринга.
Похожие темы:
Категория: Классические формализации понятия "алгоритм"
Изучить структурную и функциональную организацию машины Поста.
Краткая теоретическая часть.
Различают начальное и конечное состояния машины. Эти состояния определяются условием прикладной задачи. Рассматривая задачи, решаемые с применением машины Поста, будем говорить о начальном состоянии ленты и положении каретки, а после действия - о конечном состоянии ленты и положении каретки. Например, начальное состояние ленты не изменилось, но каретка переместилась на один шаг (позицию) и изменилось значение в секции ленты, в которую находится каретка.
Требование к переводу машины из начального в конечное состояние определяет цель действия. Эта цель формулируется каждый раз, как возникает новая прикладная задача.
Структурная организация элементов машины Поста.
Структурная схема модели машины Поста представлена на рисунке 1.
| Устройство управления |
| Интерфейс |
| Исполнительное устройство |
| Память программ |
Рисунок 1 – Структурная схема модели машины Поста
Как видно из рисунка, модель машины Поста состоит из основных блоков:
· Интерфейса, который предназначен для организации работы пользователя с машиной;
· Памяти программ, которая предназначена для хранения команд пользователя;
· Управляющего устройства, которое производит дешифрацию команды и создает управляющие сигналы для их выполнения;
· Исполнительного устройства, которое исполняет команду пользователя, производя действия исходя из управляющих сигналов.
Каретку можно реализовать при помощи двух дешифраторов DC и мультиплексора MX, которые соединены с регистром данных. Перемещение каретки может задаваться при помощи адреса, генерируемого счетчиком СТ.
Синхронизация операции записи/чтения и перемещения каретки определяется программой или последовательностью команд машины. Действия каретки определены типом операции, указанной в команде.
Устройство управления определяет тип операции, хранимой в регистре команд (RGK), и вырабатывает с помощью дешифратора команд DC(1-5) соответствующие синхронизирующие сигналы Y(1-5).
Запись программы осуществляется при помощи терминала c возможностью непосредственного обращения к памяти программ. Выборка команд из этой памяти осуществляется благодаря адресации к памяти программ и порта ввода-вывода. Так, например, на начальном этапе работы машины, после того, как был произведен аппаратный сброс, пусковой адрес устанавливается равным 1 и далее он определяется при помощи адресной части команды (В или С операнд).
Машина Поста и ЭВМ.
· Вся информация, обрабатываемая в машине, представляется в двоичном виде и распределяется в элементах памяти.
· Как для машины Поста, так и для ЭВМ, указывается некоторый ограниченный набор элементарных операций (действий). За один шаг, ЭВМ, как и машина Поста, может совершить какое-либо действие из этого набора.
· Машина Поста, как и ЭВМ, работает по программе, указывающей, какие действия, и в каком порядке должны быть выполнены.
· Доступ к данным в машине Поста возможен только линейно (последовательный доступ), тогда как ЭВМ имеет ОЗУ с произвольным доступом. Чтобы из одной секции перейти к другой, каретка должна пройти все промежуточные секции.
· В архитектуре ЭВМ, при выполнении программы, порядок выполнения команд определяется исходя из внутреннего состояния специального регистра – счетчика команд, тогда как в машине Поста последовательность выполнения команд определяется в самой программе (В операнд).
Организация машины Поста
Исполнительное устройство (ИУ) включает в себя имитатор ленты и имитатор каретки. Имитатор ленты представляет собой набор триггеров, каждый из которых может хранить бит информации. Лента является общим понятием хранилища данных. Современные вычислительные средства реализуют функцию хранения посредством регистров.
Имитатор каретки обеспечивает позиционирование напротив активной секции. Если пронумеровать секции, то каретка должна последовательно обращаться к заданным номерам (например, начальное положение каретки).
Адресация активной секции является функцией счетчика секций (CчС). Так как счетчик секций осуществляет двоичный счет, то на базе счетчика можно имитировать сдвиги каретки влево (СчС: = СчС+1) или вправо (СчС: = СчС-1).
Отсылка, выбранная с помощью коммутатора, В - нижняя или С - верхняя, является адресом, который поступает в память для выборки очередной команды. Команды, сформированные списком, как показаны в таблице 1. Порядковый номер в списке определяет код операции (КОП). В столбце КОП показана двоичная запись одноименного номера.
В таблице 1 выделены следующие группы операций:
Эти сигналы могут быть отображены функцией, которая реализуется дешифратором команд DC, как показано на рисунке 4.
Рисунок 2 – Дешифратор команд
Рисунок 2 - Мультиплексор отсылок
Память программ предназначена для хранения команд пользователя. Запись этих команд осуществляется при помощи терминала в режиме прямого доступа к памяти. При выполнении программы, по шине данных передается адрес команды, по которому из определенной ячейки памяти извлекается команда, которая отображается на шине данных.
Структура машины Поста
Справа на рисунке 1 дано обобщенное описание оперативного запоминающего устройства (RAM) и терминала. Оперативное запоминающее устройство связано посредством шины адресной (шА) и шины данных (шD) с процессором (все, что размещено на рисунке левее ОЗУ и терминала).
Модель разработана с целью демонстрации одной из традиционных формализаций понятия процессор наряду с такими формализациями, как машина Тьюринга и т.п.
Управление моделирующей программой осуществляется в диалоговом режиме экранного редактирования путем выбора соответствующего пункта меню. Пояснительные надписи, комментирующие смысл необходимых действий, выводятся на экран.
Результаты работы программ представлены на экране в виде динамических картинок состояния элементов, узлов и устройств машины в процессе интерпретации команд программы пользователя.
При создании программной модели машины Поста в структуру обучающей системы были введены следующие ограничения:
· состав машины Поста определен минимальной конфигурацией, которая включает в себя: процессор, детализированный до уровня: триггер, регистры, мультиплексор, счетчик, шины; оперативное запоминающее устройство, детализированное до уровня: элемент памяти, матрица запоминающих элементов, адресные дешифраторы столбцов и строк матрицы, порт ввода-вывода, регистры и шины; пультовый терминал; системная магистраль, детализированная до уровня шина адреса, шина данных, сигнал управления записи/чтения;
· система команд (в смысле Поста) должна быть минимальной (не более шести), но достаточной для построения алгоритмических структур следования, ветвления и циклов;
· адресное пространство программной памяти - 99 десятичных слов (в модели ограничено 32 адресами, что достаточно для учебных целей), а регистр данных, т.е. лента в смысле Поста - 32-разрядный;
На первом этапе работы с обучающей системой предусмотрено изучение разделов: анализ системы команд (6 команд); организация ветвлений и циклов; примеры программирования.
На втором этапе, многоуровневая система меню предлагает исследователю:
· получить справочную информацию по работе и организации машины Поста;
· ознакомиться с примерами решения типовых задач (например, тест системы команд) и, при желании, повторить их на демонстрационных динамических рисунках;
При этом, система подсказок позволяет закрепить последовательность и содержание шагов решения задачи, а динамические рисунки отражают ситуации на объекте и создает эффект работы с реальной средой.
Запуск и работа с автоматизированной обучающей системой
Для того чтобы запустить модель необходимо открыть cesir\vm\ОЭВМиВС и скопировать на компьютер диск D папку OEVM Win XP. После этого запустите с помощью ярлыка на рабочем столе программу vmware player.
Программа АОС 0 позволяет решать три задачи:
· Анализ структуры машины: операционный и управляющий автоматы процессора; оперативная память; пультовый терминал; шины связи устройств.
· Организация шин адресов, данных и управления; структура оперативной памяти и организация записи/чтения данных через порт ввода-вывода.
· Изучение алгоритма работы машины Поста при интерпретации команд на примере TEST-программы системы команд (находится в директории AOS0). Анализ алгоритма программы тестирования. Синтез программы по заданному алгоритму модели элемента 2 И-НЕ.
Интерфейс обучающей системы решает следующие задачи:
- вывод на экран структурной схемы;
- поддержку функциональных клавиш F2- F7;
- визуализацию процессов передачи, хранения и обработки данных и команд.
| Да |
| Нет |
| Да |
| Нет |
| Да |
| Нет |
| Да |
| Нет |
| Да |
| Да |
| Да |
| Да |
| Да |
| Нет |
| Нет |
| Нет |
| Нет |
| Нет |
| Нет |
| Да |
| НАЧАЛО |
| КОНЕЦ |
| RGK: КОП = 1? |
| M:RA = 1 |
| Начальное состояние СчС СТ = 0 |
| Установка пускового адреса (ПА) |
| Чтение |
| М = 1? |
| Память занята? |
| M:RS = КОП.В.С |
| RGK: КОП = 5? |
| RGK := RS |
| RD(СчС) := 1 |
| RGK: КОП = 2? |
| RD(СчС) := 0 |
| RGK: КОП = 3? |
| RD(СчС) := СчС+1 |
| RGK: КОП = 4? |
| RD(СчС) := СчС-1 |
| RGK: КОП = 0? |
| ЛУ :=0 |
| ОСТАНОВ |
| ЛУ: = RD(CчC) |
| ЛУ = 1? |
| MUXотсыл. : = C |
| СТОП = 1? |
| MUXотсыл. : = B |
| ЛУ :=0 |
| Аварийная остановка |
| P = 1? |
| M:RA := MUXотсыл |
Рисунок 3 – Блок схема алгоритма работы машины Поста
3 Задание к лабораторной работе
· Исследовать структуру машины Поста;
· Изучить организацию шин адресов, данных и управления;
· Исследовать элементную базу процессора машины;
· Изучить поведение машины Поста по блок-схеме алгоритма ее работы;
Эмиль Леон Пост (англ. Post Emil Leon, 11 февраля1897, Августов, Царство Польское, Российская империя) — 21 апреля1954, Нью-Йорк, США) — американскийматематик и логик; один из основателей многозначной логики (1921); основные труды по математической логике: алгебра Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0 , либо помеченной меткой 1 . За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
После программы запуска возможны варианты:
Читайте также: