Архитектура машины поста выберите состав машины поста

Машина Поста

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

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из …

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

i K j,

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

У команды «стоп» отсылки нет.

Варианты окончания выполнения программы на машине Поста:

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

Пример работы машины Поста:

Источник

Машина Поста (устройство, команды и принцип работы)

Содержимое разработки

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

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

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Структура машины Поста:

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

Т.о., Пост сократил алфавит всего до двух цифр. Это допустимо, потому что любые данные можно перекодировать в двоичный код, сопоставив каждой букве исходного алфавита уникальную последовательность нулей и единиц.

Алгоритм работы машины Поста задается не в виде таблицы, а как программа для универсального исполнителя.

Программа состоит из конечного числа строк и использует всего 6 команд.

где N. — номер строки, J — строка на которую переходит управление далее.

Попытка стереть метку там, где ее нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается.

Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки).

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

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

— работа может закончиться командой Stop;

— работа никогда не закончится.

Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0,n1). С помощью этой команды можно также строить циклы, как с предусловием, так и с постусловием.

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

После команд «←”, «→”, «0” и «1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает «переместить каретку влево и перейти на строку 3”.

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

1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.

2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.

Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).

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

Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:

Источник

Практическая работа, Машина Поста

Изучение машины Поста в школьном курсе информатики

Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на “примитивность” машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

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

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

В статье предлагается материал для практикума по теме “Машина Поста” в рамках изучения основ алгоритмизации. Практикум включает в себя теоретическую часть и набор задач с решениями.

Теоретическая часть. Состав машины Поста

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

Рис. 1. В каждый момент времени каретка указывает на одну из ячеек

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

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

Будем говорить, что мы можем применить программу к текущему состоянию машины Поста, если выполнение программы не приведет к зацикливанию, т.е. рано или поздно мы выполним команду останов.

Пример программы, которая не применима ни к одному состоянию машины Поста:

Рассмотрим задачу для машины Поста и ее решение.

Программа для машины Поста:

Практическая часть практикума “Машина Поста”

Все задачи практикума сгруппированы по темам. Начинать знакомство с машиной Поста рекомендуется с первой темы “Применимость программ. Определение результата выполнения программ”.

Пояснения к условиям задач

1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.

2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n.

3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: nподряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.

К примеру, запись “12012” будет соответствовать записи “11011” на ленте.

4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.

1. Применимость программ. Определение результата выполнения программ

1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.

c) 1) зацикливание (…111)

2) зацикливание (…1111001)

3) зацикливание (1010111…)

2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.

Пояснение : выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в начальный момент времени.

3. Написать программы для машины Поста, которые обладают следующими свойствами:

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

2. Арифметические задачи

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

4. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

3. –> 4 (команды 3 и 4 — передвигаем каретку к концу массива)

5. V 6 (команды 5–7 — ставим 2 метки в конце массива)

5. Даны два массива меток, которые находятся на не-
котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

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

7. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

1. Ищем правый край массива m, двигаясь слева направо.

2. Стираем правую метку массива m.

3. Ищем правый край массива n, двигаясь слева направо.

4. Стираем левую метку массива n.

5. Проверяем, мы стерли последнюю метку в массиве n (в этом случае следующая справа ячейка должна быть пустой)?

6. Если стерли последнюю метку, то конец алгоритма.

7. Иначе ищем правый конец массива m, двигаясь справа налево.

8. Переход на шаг 2.

1. –> 2 (команды 1–3: ищем левую метку массива m)

4. X 5 (стираем левую метку массива m)

7. X 8 (стираем левую метку массива n)

8. На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.

4. X 5 (удаляем крайний правый элемент 1-го массива)

9. X 10 (удаляем первую метку 2-го массива)

14. –> 15 (мы удалили полностью 1-й массив)

9. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.

10. На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.

11. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.

3. Ориентация на ленте

12 На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

13. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.

1. X 2 (удаляем левую метку массива)

4. V 5 (ставим справа от массива метку, раннее нами была удалена самая левая метка)

9. –> 1 (и начинаем все сначала)

14. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.

1. V 2 (выставили левую метку)

5. V 6 (выставили правую метку)

8. X 9 (стираем левую метку)

11. V 12 (передвигаем левую метку)

12. –> 13 (ищем правую метку)

14. X 15 (стираем правую метку)

15. –> 3 (повторяем действия)

4. Действия над заданным на ленте множеством меток

15. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.

17. X 18 (удаляем метку, соответствующую исходному положению каретки)

16. На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали nрасположенных подряд ячеек.

6. X 7 (удаляем четный массив)

18. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.

19. На ленте машины Поста расположен массив из 2n – 1 меток. Составить программу удаления средней метки массива.

14. V 15 (дошли до левого конца)

19. V 9 (дошли до правого конца)

20. На ленте машины Поста расположен массив из 2n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива.

21. Написать программу, которая осуществляет преобразование 1 n 01 m –> 1 m 01 n (n 1 и m 1).

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

Решение аналогично нахождению разности двух чисел.

23. На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.

Решение аналогично нахождению разности двух чисел.

24. Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Источник

Краткая теоретическая часть.

ЛАБОРАТОРНАЯ РАБОТА ОРГАНИЗАЦИЯ МАШИНЫ ПОСТА

Цель работы

Изучить структурную и функциональную организацию машины Поста.

Краткая теоретическая часть.

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

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

Структурная организация элементов машины Поста.

Структурная схема модели машины Поста представлена на рисунке 1.

Рисунок 1 – Структурная схема модели машины Поста

Как видно из рисунка, модель машины Поста состоит из основных блоков:

· Интерфейса, который предназначен для организации работы пользователя с машиной;

· Памяти программ, которая предназначена для хранения команд пользователя;

· Управляющего устройства, которое производит дешифрацию команды и создает управляющие сигналы для их выполнения;

· Исполнительного устройства, которое исполняет команду пользователя, производя действия исходя из управляющих сигналов.

Для того, чтобы имитировать ленту машины Поста достаточно иметь регистр данных RD, который можно построить при помощи RS-триггеров. В этом случае одной секции соответствует один триггер, который может хранить бинарную информацию («1» или «0»).

Каретку можно реализовать при помощи двух дешифраторов DC и мультиплексора MX, которые соединены с регистром данных. Перемещение каретки может задаваться при помощи адреса, генерируемого счетчиком СТ.

Синхронизация операции записи/чтения и перемещения каретки определяется программой или последовательностью команд машины. Действия каретки определены типом операции, указанной в команде.

Устройство управления определяет тип операции, хранимой в регистре команд (RGK), и вырабатывает с помощью дешифратора команд DC(1-5) соответствующие синхронизирующие сигналы Y(1-5).

Запись программы осуществляется при помощи терминала c возможностью непосредственного обращения к памяти программ. Выборка команд из этой памяти осуществляется благодаря адресации к памяти программ и порта ввода-вывода. Так, например, на начальном этапе работы машины, после того, как был произведен аппаратный сброс, пусковой адрес устанавливается равным 1 и далее он определяется при помощи адресной части команды (В или С операнд).

Машина Поста и ЭВМ.

· Вся информация, обрабатываемая в машине, представляется в двоичном виде и распределяется в элементах памяти.

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

· Машина Поста, как и ЭВМ, работает по программе, указывающей, какие действия, и в каком порядке должны быть выполнены.

· Доступ к данным в машине Поста возможен только линейно (последовательный доступ), тогда как ЭВМ имеет ОЗУ с произвольным доступом. Чтобы из одной секции перейти к другой, каретка должна пройти все промежуточные секции.

· В архитектуре ЭВМ, при выполнении программы, порядок выполнения команд определяется исходя из внутреннего состояния специального регистра – счетчика команд, тогда как в машине Поста последовательность выполнения команд определяется в самой программе (В операнд).

Организация машины Поста

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

Имитатор каретки обеспечивает позиционирование напротив активной секции. Если пронумеровать секции, то каретка должна последовательно обращаться к заданным номерам (например, начальное положение каретки).

Адресация активной секции является функцией счетчика секций (CчС). Так как счетчик секций осуществляет двоичный счет, то на базе счетчика можно имитировать сдвиги каретки влево (СчС: = СчС+1) или вправо (СчС: = СчС-1).

Операции записи обеспечиваются передачей управляющих сигналов на соответствующий вход R или S триггера, что позволяет записать в активную секцию «0» или «1». Чтение состояния секции обеспечивается коммутатором (мультиплексор), для которого адрес активной секции указывает счетчик секций.

Имитатор УУ содержит коммутатор отсылок В и С, которые указывают на адрес следующей команды. Выбор отсылки определен состоянием линии управления (ЛУ), которое вычисляется ИУ при выполнении команды в зависимости от состояния активной секции ленты и сигнала У5 по логике «И».

В таблице 1 выделены следующие группы операций:

При выполнении команды «Останов» никакие управляющие сигналы не генерируются и выполнение программы прекращается.

Эти сигналы могут быть отображены функцией, которая реализуется дешифратором команд DC, как показано на рисунке 4.

Рисунок 2 – Дешифратор команд

В состав УУ входит коммутатор отсылок, который выполнен при помощи мультиплексора, как показано на рисунке 2. Его таблица истинности приведена в таблице 2. Графа «А» таблицы 2 назначается после вычисления логических условий (ЛУ) в операционном автомате, где выделяется состояние активной секции («0», «1»). Это состояние передается в графу «А» при выполнении команды «Решение». Однако, при выполнении других команд, значение ЛУ определено нулю. Графа MUX определяет значение выхода функции. Это значение соответствует отсылкам В или С, коммутируемым в зависимости от значения графы А.

Терминал предназначен для указания режима работы (ПДП или ВЫЧИСЛЕНИЯ), а также для управления «Пуском» машины или продолжением выполнении программы. Кроме того, с пульта управления оператор указывает пусковой адрес (ПА).

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

Структура машины Поста

При детальном рассмотрении рисунка 1 «слева направо» и «сверху вниз, можно заметить, что регистр данных RD(n-0) в каждом разряде (секции) имеет R-S триггер, входы S триггеров подключены к соответствующим выходам дешифратора DCS, а входы R – к соответствующим выходам дешифратора DCR. Например, сигналы DCS(0) и DCR(0) подключены соответственно ко входам S и R нулевого разряда регистра RD(n-0). Выходы RD(n-0) подключены ко входам мультиплексора MX, выход которого образует результат «РЕЗ» и подключен к R-S-триггеру, а выход этого R-S-триггера связан с одним входом логической схемы «И». Состояние выхода элемента «И» определяет условия выбора номера следующей команды программы. Выход элемента «И» подключен к адресной зоне мультиплексора MX. (т.н. мультиплексор отсылок). Из рисунка 1 видно, что такие отсылки названы В и С (выход мультиплексора). Слова В и С поступают с выхода регистра команд RGK.

Справа на рисунке 1 дано обобщенное описание оперативного запоминающего устройства (RAM) и терминала. Оперативное запоминающее устройство связано посредством шины адресной (шА) и шины данных (шD) с процессором (все, что размещено на рисунке левее ОЗУ и терминала).

Шина адреса (шА) подключена ко входу регистру адреса (RA) памяти ОЗУ и соединена с выходом мультиплексора отсылок и пультовым терминалом. Шину шА загружают отсылкой (В, С) с выхода мультиплексора отсылок по команде «Р» (продолжить), которая формируется с пультового терминала.

Шина шD связывает ОЗУ с регистром RGK команд и терминалом. ОЗУ имеет порт ввода-вывода RS (регистр слова). Передача слова из порта RS на RGK возможна при условии, что клавиша Р (продолжить) не нажата, другими словами, команда «Р» пультового терминала не введена, и был произведен запуск программы («ПУСК»). Через порт RS в память по шине шD данные вводятся с пультового терминала (управляющий сигнал «W»).

Модель «Машина Поста»

Модель разработана с целью демонстрации одной из традиционных формализаций понятия процессор наряду с такими формализациями, как машина Тьюринга и т.п.

Управление моделирующей программой осуществляется в диалоговом режиме экранного редактирования путем выбора соответствующего пункта меню. Пояснительные надписи, комментирующие смысл необходимых действий, выводятся на экран.

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

При создании программной модели машины Поста в структуру обучающей системы были введены следующие ограничения:

· состав машины Поста определен минимальной конфигурацией, которая включает в себя: процессор, детализированный до уровня: триггер, регистры, мультиплексор, счетчик, шины; оперативное запоминающее устройство, детализированное до уровня: элемент памяти, матрица запоминающих элементов, адресные дешифраторы столбцов и строк матрицы, порт ввода-вывода, регистры и шины; пультовый терминал; системная магистраль, детализированная до уровня шина адреса, шина данных, сигнал управления записи/чтения;

· система команд (в смысле Поста) должна быть минимальной (не более шести), но достаточной для построения алгоритмических структур следования, ветвления и циклов;

На первом этапе работы с обучающей системой предусмотрено изучение разделов: анализ системы команд (6 команд); организация ветвлений и циклов; примеры программирования.

На втором этапе, многоуровневая система меню предлагает исследователю:

· получить справочную информацию по работе и организации машины Поста;

· ознакомиться с примерами решения типовых задач (например, тест системы команд) и, при желании, повторить их на демонстрационных динамических рисунках;

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

Запуск и работа с автоматизированной обучающей системой

Для того чтобы запустить модель необходимо открыть cesir\vm\ОЭВМиВС и скопировать на компьютер диск D папку OEVM Win XP. После этого запустите с помощью ярлыка на рабочем столе программу vmware player.

В открывшемся окне выберете пункт «open a virtual machine» и затем укажите путь до того места где лежит файл виртуальной машины.

После запуска виртуальной машины откройте на рабочем столе папку «MAC_POST.AOS». В данной директории найдите файл с именем «aos0.bat» и запустите его. Ознакомьтесь со структурной схемой машины, выделите основные блоки. Обратите внимание на функциональное назначение клавиш, показанных по периметру экрана. Начните с записи команды в память (клавиша F2) в соответствии с примером. Программа АОС 0 покажет Вам подробности процесса. При выполнении команд программы в режиме, определяемом клавишей F4, следите за подсказками.

Изучите структурную схему машины, выведенной на экран. Выделите основные элементы: УУ, ИУ, ОЗУ, терминал, системные шины. Обратите внимание на «окна» и функциональные клавиши.

Воспользуйтесь клавишей F6 «Пример работы». В меню выберите «Тест команд». В окне «Программа» появится текст программы. Проверьте ход исполнения шагов программы и соответствие со схемой алгоритма «TEST». Клавиша F4 «Запуск» откроет меню – «По шагам», ENTER. Следите за подсказками системы. Продвижение по шагам программы – клавиша «ПРОБЕЛ».

Программа АОС 0 позволяет решать три задачи:

· Анализ структуры машины: операционный и управляющий автоматы процессора; оперативная память; пультовый терминал; шины связи устройств.

· Организация шин адресов, данных и управления; структура оперативной памяти и организация записи/чтения данных через порт ввода-вывода.

· Изучение алгоритма работы машины Поста при интерпретации команд на примере TEST-программы системы команд (находится в директории AOS0). Анализ алгоритма программы тестирования. Синтез программы по заданному алгоритму модели элемента 2 И-НЕ.

Исследование поведения работы машины Поста следует с изучения схемы алгоритма, который представлен в виде блок-схемы на рисунке 3. Видно, что функционирование машины начинается с обращения к ОЗУ за выборкой команды программы (3). Далее осуществляется пересылка команды в процессор (4). Затем организована дешифрация поля формата команды (5, 6, 7, 8, 14, 15) и выполнение соответствующей микрооперации (9, 10, 11, 12, 16). При этом формируются логические условия (13, 17), по которым процессор определяет адрес следующей команды программы. Процесс продолжается до конца программы или вмешательства («СТОП») пользователя.

Интерфейс обучающей системы решает следующие задачи:

— вывод на экран структурной схемы;

— поддержку окон «Программа» и «Данные»;

— поддержку функциональных клавиш F2- F7;

— поддержку «Меню» для записи в память и исполнения команд программы;

— визуализацию процессов передачи, хранения и обработки данных и команд.

Рисунок 3 – Блок схема алгоритма работы машины Поста

3 Задание к лабораторной работе

· Исследовать структуру машины Поста;

· Изучить организацию шин адресов, данных и управления;

· Исследовать элементную базу процессора машины;

· Изучить поведение машины Поста по блок-схеме алгоритма ее работы;

· Составить алгоритм и программу, моделирующую работу логического элемента «2И». Пусть входные значения элемента будут находиться в ячейках RD0, RD1, а результат работы будет записываться в ячейку памяти RD2;

Источник