Напишите программу для машины поста которая увеличивает на 1 число записанное в унарной системе

Практическая работа № 37
«Машина Поста»

Файлы-заготовки для выполнения этой практической работы

1. Что делает следующая программа для машины Поста?

Как она будет работать при различных начальных состояниях ленты?

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

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

4. Решите задачу 2 при условии, что в начале работы каретка расположена где-то справа от записи числа.

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

6. На ленте расставлены метки, между которыми могут быть пропуски длиной в одну ячейку. Заполнить все пропуски метками. Каретка стоит над самой левой меткой.

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

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

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

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

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

Источник

Машина Поста

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример работы машины Поста : прибавление к числу единицы.

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

Вопросы:

1. Сравните машины Тьюринга и Поста.

2. Зачем нумеруются строки в программе для машины Поста?

Задачи:

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

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

Как будет работать каждая из программ при различных начальных состояниях ленты?

Компьютерный практикум:

(Методические материалы И.Г. Семакина)

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

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

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

Машина Поста программа (К.Поляков)

Дополнительные источники:

1. К.Ю. Поляков, Е.А. Еремин «Элементы теории алгоритмов». Журнал «Информатика» №1, 2012 г.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Практическая работа № 25. Машина Поста

1. Что делает следующая программа для машины Поста?

Как она будет работать при различных начальных состояниях ленты?

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

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

4. Решите задачу 2 при условии, что в начале работы каретка расположена где-то справа от записи числа.

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

6. На ленте расставлены метки, между которыми могут быть пропуски длиной в одну ячейку. Заполнить все пропуски метками. Каретка стоит над самой левой меткой.

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

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

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

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

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

Источник

Напишите программу для машины поста которая увеличивает на 1 число записанное в унарной системе

МАШИНЫ ПОСТА И ТЬЮРИНГА

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

Алгоритм вычитания целых чисел для машины Поста приведен ниже. В первых двух строчках указывается положение каретки и состояние ленты, на которой в унарной системе счисления записаны два числа (в данном случае 6 и 4). В результате исполнения программы на ленте останется число 2 в унарной системе счисления.

Рис. 1. Вычитание целых чисел.

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

Алгоритм увеличения целого числа на 2 представлен ниже:

Для реализации этого алгоритма в процедуру Programma программы ПР-1 необходимо вставить следующий код:

Рис. 2. Увеличение числа на 2

Напишите компьютерную программу, моделирующую машину Поста, которая уменьшает целое число на 2.

Пусть на ленте машины Поста записано число 6, каретка находится напротив левой ячейки (координата x=1). Для вычитания из любого целого N числа 2 в процедуру Programma программы ПР-1 следует вставить следующий код:

Рис. 3. Уменьшение целого числа на 2

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

Программа сложения целых чисел на машине Поста выглядит так:

В программу ПР-1 следует вставить код:

Рис. 4. Сложение двух целых чисел

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

Результат решения представлен на рис. 5. Возможен другой способ решения:

Рис. 5. Умножение целого числа на 2

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

Используется программа ПР-2. Состояние ленты машины Тьюринга записывается в массиве:

Программа для машины Тьюринга записывается в виде последовательности команд, представленных в общепринятом формате:

Программа для машины Тьюринга, увеличивающая целое число на 2, состоит из 3 команд:

Рис. 6. Увеличение целого числа на 2

Напишите программу для МТ, складывающую два целых числа, заданных набором единиц.

В программу ПР-2 следует вставить код:

Результат работы программы представлен на рис. 7.

Рис. 7. Сложение целых чисел

Пусть машина Тьюринга находится в состоянии 1. В компьютерную программу ПР-2 необходимо вставить следующий код:

Рис. 8. Замена единиц на звездочки и пробелы

Программа для машины Тьюринга имеет вид:

Для решения этой задачи в программу ПР-2 следует вставить код:

Результат работы программы представлен на рис.9.

Рис. 9. Замена единиц на звездочки

Программа для машины Тьюринга выглядит так:

В компьютерную программу ПР-2 следует вставить код:

Рис. 10. Группировка символов A

Программа для машины Тьюринга представлена в таблице:

В программу ПР-2 следует вставить код:

Рис. 11. Увеличение числа на 1.

Тексты программ находятся в zip-архиве, файл gl-14.pas.

Источник