Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из …
1. бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
2. головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.
Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
С++ потоки и методы класса | С++ метод класса в потоке | Многопоточное программирование | C++ #5
Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
I K j,
где i — номер команды, K – действие каретки, j — номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
· V j — поставить метку, перейти к j-й строке программы.
· X j — стереть метку, перейти к j-й строке программы.
· -> j — сдвинуться вправо, перейти к j-й строке программы.
·? j1; j2 — если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
·! – конец программы (стоп).
У команды «стоп» отсылки нет.
Варианты окончания выполнения программы на машине Поста:
1. Команда «стоп» — корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).
Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга.
Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.
Пример работы машины Поста:
Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Информатика, Северов Д. С., 16.04.2021
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2? 1;3
3 4 V 5
5!
А процесс выполнения может быть таким:
Машина Тьюринга
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Что собой представляет машина Тьюринга?
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
· Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
· Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
· Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
· Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
· Передвигаться на одну ячейку влево или вправо.
· Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Источник: poisk-ru.ru
Лабораторки / ЛР3
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР) Кафедра комплексной информационной безопасности электронно- вычислительных систем (КИБЭВС) ОРГАНИЗАЦИЯ МАШИНЫ ПОСТА Отчет по лабораторной работе №3 по дисциплине «Организация ЭВМ и вычислительных систем» Студенты гр. 10.11.2020 Приняла Доцент кафедры КИБЭВС _______ 10.11.2020
Томск 2020
2 1 Введение Цель работы: изучение принципов работы простейшего управляющего устройства (УУ) на примере машины Поста. Задание: 3-ИЛИ-НЕ (4 Вариант).
3 2 Ход работы: 2.1. Основные теоретические сведения Машина Поста — это абстрактная, но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ не должно вызывать трудностей.
Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. Машина Поста состоит из неподвижной ленты и каретки. По ленте влево — вправо движется сенсорная, чувствительная каретка с возможностью записи данных («1» или «0») в секции и их чтения.
Каретка в неподвижном состоянии находится на одной секции, а за единицу времени (такт), по команде, каретка может сместиться только на одну секцию. Состояние ленты может меняться в процессе работы машины. Тогда, состояние машины — это состояние ленты и положение каретки (номер секции на которой находится каретка). Различают начальное и конечное состояния машины.
Эти состояния определяются условием прикладной задачи. Рассматривая задачи, решаемые с применением машины Поста, будем говорить о начальном состоянии ленты и положении каретки, а после действия — о конечном состоянии ленты и положении каретки. Схема рассматриваемой модели машины Поста представлена на рисунке 1.
4 Рисунок 1 – Схема модели машины Поста Как видно из рисунка 1, модель машины Поста состоит из основных блоков: интерфейса, который предназначен для организации взаимодействия пользователя с машиной; памяти программ, которая предназначена для хранения команд пользователя; управляющего устройства, которое производит дешифрацию команды и создает управляющие сигналы для их выполнения; исполнительного устройства, которое исполняет команду пользователя, производя действия исходя из управляющих сигналов. Исполнительное устройство (ИУ) включает в себя имитатор ленты и имитатор каретки. Имитатор ленты представляет собой набор триггеров, каждый из которых может хранить бит информации. Лента является общим понятием хранилища данных. Современные вычислительные средства реализуют функцию хранения посредством регистров. Регистр данных (RD), имитирует секции ленты, представлен в виде набора RS-триггеров, каждый из которых имеет два входа: первый (S) — запись
5 «1», второй (R) -запись «0». Прямой выход триггера отображает состояние триггера, т.е. после того, как была произведена запись значения в триггер, это значение будет представлено на его выходе. В этом случае одной секции соответствует один триггер.
Операции записи обеспечиваются передачей управляющих сигналов на соответствующий вход R или S триггера, что позволяет записать в активную секцию «0» или «1». Чтение состояния секции обеспечивается коммутатором (мультиплексор), для которого адрес активной секции указывает счетчик секций. Имитатор каретки обеспечивает позиционирование напротив активной секции.
Если пронумеровать секции, то каретка должна последовательно обращаться к заданным номерам (например, начальное положение каретки). Каретку можно реализовать при помощи двух дешифраторов DC и мультиплексора MX, которые соединены с регистром данных. Перемещение каретки может задаваться при помощи адреса, генерируемого счетчиком СТ.
Адресация активной секции является функцией счетчика секций (CчС). Так как счетчик секций осуществляет двоичный счет, то на базе счетчика можно имитировать сдвиги каретки влево (СчС: = СчС+1) или вправо (СчС: = СчС- 1). Синхронизация операции записи/чтения и перемещения каретки определяется программой или последовательностью команд машины.
Действия каретки определены типом операции, указанной в команде. Устройство управления (УУ) в соответствии с его функциями хранит слово «команда», пока не закончено ее исполнение. Поэтому для хранения информации команды можно использовать специальный регистр команд (RGK). В RGK выделим три поля: поле КОП – действия, поле В — нижней и С — верхней отсылки к следующим командам. Устройство управления определяет тип операции, хранимой в регистре команд (RGK), и вырабатывает с помощью дешифратора команд DC(1-5) соответствующие синхронизирующие сигналы Y(1-5).
6 Имитатор УУ содержит коммутатор отсылок В и С, которые указывают на адрес следующей команды. Выбор отсылки определен состоянием линии управления (ЛУ), которое вычисляется ИУ при выполнении команды в зависимости от состояния активной секции ленты и сигнала У5 по логике «И».
Отсылка, выбранная с помощью коммутатора, В — нижняя или С — верхняя, является адресом, который поступает в память для выборки очередной команды. Команды, сформированные списком, как показаны в таблице 1. Порядковый номер в списке определяет код операции (КОП). В столбце КОП показана двоичная запись одноименного номера.
Терминал предназначен для указания режима работы (ПДП или ВЫ- ЧИСЛЕНИЯ), а также для управления «Пуском» машины или продолжением выполнении программы. Кроме того, с пульта управления оператор указывает пусковой адрес (ПА). В таблице 1 выделены следующие группы операций поддерживаемые машиной Поста: позиции 1-2 — группа «Запись» в активную ячейку; позиции 3-4 — группа «Сдвиг»; позиция 5 — команда «Решение»; позиция 6 — команда «Останов». Таблица 1
| п/п | Оператор (КОП) | Сигналы микроопераций | |||||
| Мнемоника КОП | Двоичный | Y1 | Y2 | Y3 | Y4 | Y5 | |
| код КОП | |||||||
| 1 | Запись «1» | 001 | 1 | ||||
| 2 | Запись «0» | 010 | 1 | ||||
| 3 | Сдвиг | 011 | 1 | ||||
| 4 | Сдвиг | 100 | 1 | ||||
| 5 | 1/C RD = 1? 0/В | 101 | 1 | ||||
| 6 | Останов | 000 | |||||
7 При выполнении команды «Останов» никакие управляющие сигналы не генерируются и выполнение программы прекращается. В графе «Сигналы микроопераций» указаны наименования сигналов управления и момент их активизации — логическая «1».
Эти сигналы могут быть отображены функцией, которая реализуется дешифратором команд DC, как показано на рисунке 4. Рисунок 2 – Дешифратор команд Дешифраторы DCS и DCR использованы для записи «1» и «0» в секцию регистра, а мультиплексор для чтения состояния секции, указанной счетчиком СТ. Входы С (синхронизация) дешифраторов и входы (+1, -1) счетчика подключены к источнику управляющих сигналов (У), хотя на рисунке это явно не показано.
Такие сигналы вырабатывает дешифратор кодов операций (КОП), подключенный к полю КОП регистра команд RGK. Сигнал У5 поступает на другой вход логического элемента «И», который определяет условие выбора отсылки В или С. Справа на рисунке 1 дано обобщенное описание оперативного запоминающего устройства (RAM) и терминала. Оперативное запоминающее устройство связано посредством шины адресной (шА) и шины данных (шD) с процессором (все, что размещено на рисунке левее ОЗУ и терминала). Шина адреса (шА) подключена ко входу регистру адреса (RA) памяти ОЗУ и соединена с выходом мультиплексора отсылок и пультовым терминалом. Шину шА загружают отсылкой (В, С) с выхода мультиплексора отсылок по команде «Р» (продолжить), которая формируется с пультового терминала.
8 Шина шD связывает ОЗУ с регистром RGK команд и терминалом. ОЗУ имеет порт ввода-вывода RS (регистр слова). Передача слова из порта RS на RGK возможна при условии, что клавиша Р (продолжить) не нажата, другими словами, команда «Р» пультового терминала не введена, и был произведен запуск программы («ПУСК»).
Через порт RS в память по шине шD данные вводятся с пультового терминала (управляющий сигнал «W»). Ко входам WO и W1 элемента RAМ подключена схема (четыре логических элемента) выбора режима «чтение-запись» работы ОЗУ. Эта схема синхронизируется сигналом «W», т.е. когда W=1 — запись, иначе — чтение.
К выходу регистра RA адреса ОЗУ подключен дешифратор, имеющий два выхода А и В, которые указывают адрес запоминающего элемента, установленного на пересечении столбцов В и строк А матрицы RAМ. 2.2. Написание программы Для того чтобы запустить модель машины Поста необходимо скачать архив «MAC_POST.AOS» из электронного курса. Распаковать этот архив и запустить файл «AOS0.bat».
Рисунок 3 – Запуск программы Для нашего задания составим таблицу истинности.
9 Таблица 2 – Таблица истинности
| m0 | m1 | m2 | m3 |
| 1 | |||
| 1 | |||
| 1 | |||
| 1 | 1 | ||
| 1 | |||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | 1 |
В ходе выполнения работы была написана программа, представленная на рисунке 4. Рисунок 4 – Готовая программа 2.3. Алгоритм и код программы и его объяснение 1) 50208 // Команда сверяет значение в начальной ячейке, если 0, то переходит к команде 2, если 1, то переходит к команде 8. 2) 30300 // Сдвиг на одну ячейку влево, переход к 3 команде. 3) 50409 // Команда сверяет значение в следующей ячейке, если 0, то переходит к 4 команде, если 1, то к 9 команде. 4) 30500 // Сдвиг на одно ячейку влево, переход к команде 5.
10 5) 50610 // Команда сверяет значение в последней ячейке, если 0, то переходит к команде 6, если 1, то переходит к команде 10. 6) 30700 // Сдвиг на одно ячейку влево, переход к 7 команде. 7) 11100 // Записывает в ячейку 3 значение 1, переход к команде 11. 8) 30900 // Сдвиг на одну ячейку влево, переход к команде 9. 9) 31000 // Сдвиг на одну ячейку влево, переход к команде 10.
10) 31100 // Сдвиг на одну ячейку влево, переход к команде 11. 11) 00000 // Конец Число в ячейке 3 — это ответ. Алгоритм программы представлен на рисунке 5.
Источник: studfile.net
Презентация на тему Машина Тьюринга
Основная идея концепции алгоритма как абстрактной машины: Если решение задачи можно описать как последовательность действий, выполняемых машиной Тьюринга или машиной Поста, то эта задача алгоритмически разрешима.
Источник: mypreza.com