Машина поста сложение двух чисел

Машина поста сложение двух чисел

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

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

Алгоритм вычитания целых чисел для машины Поста приведен ниже. В первых двух строчках указывается положение каретки и состояние ленты, на которой в унарной системе счисления записаны два числа (в данном случае 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.

Источник

Машина поста сложение двух чисел

Урок 24. Практическая работа № 7. Автоматическая обработка данных

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

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

Система команд машины Поста: (везде буква n обозначает номер текущей команды):

Задание 1

Составить программу перевода информационной ленты машины Поста из начального состояния (н.с.) в конечное (к.е.):

Задание 2

1. Выполнить на машине Поста программу:

2. Какую задачу решает исполнитель по этой программе?

3. Что произойдет, если начальное состояние информационной ленты будет иметь следующий вид?

В следующих задачах считается, что n расположенных подряд меток обозначают число n (непозиционная система счисления с основанием 1).

Задание 3

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

Задание 4

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

Указание. Стирать метки по одной у каждого числа, пока у вычитаемого не кончатся все метки.

Задание 5

Используя программу вычитания, проверить, что получится, если:

а) уменьшаемое равно вычитаемому;
б) уменьшаемое меньше вычитаемого.

Задание 6

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

Указание. Стереть каждую вторую метку; уплотнить оставшиеся метки.

Задание 7

Используя программу деления числа на 2: а) проверить, что получится для числа 2; б) модифицировать программу с учетом числа 2.

Указание. Справа от пустой клетки поставить метку, а слева стереть две метки. Так поступать до тех пор, пока слева остаются метки.

Задание 8

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

Задание 9

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

Указание. Через одну пустую клетку поставить две метки, а в исходном числе стереть одну. Так поступать, пока в исходном числе остаются метки.

Задание 10*

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

Задание 11*

Задание 12*

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

Источник

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

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

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

Составьте программу машины Поста, которая увеличивает целое число x=4 на 3
Составьте программу машины Поста, которая увеличивает целое число x=4 на 3

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

Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте машины Поста
6. Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте.

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

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

Источник

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

Постройте программу машины Поста, реализующей алгоритм перевода машинной записи числа n в машинную запись
Постройте программу машины Поста, реализующей алгоритм перевода машинной записи числа n в машинную.

Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте машины Поста
6. Составьте программу сложения двух целых неотрицательных чисел а и Ь, расположенных на ленте.

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

Постройте программу машины Поста, отыскивающую и стирающую среднюю метку массива
На ленте машины Поста расположен массив из 2n-1 отмеченных секций. Постройте программу машины.

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

Нахождение разности двух неотрицательных целых чисел a и b, находящихся на ленте машины Поста
Составить программу нахождения разности двух неотрицательных целых чисел a и b, находящихся на.

Алгоритм (блок-схема) сложения двух чисел в 2 с/с
Возник ещё один вопрос, как сделать алгоритм (блок-схему) сложения двух чисел в 2 с/с. Заранее.

Источник

Машина Поста

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

Содержание

Принцип работы

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

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

У команды «стоп» отсылки нет. После запуска возможны варианты:

Пример: вычитание натуральных чисел P — Q

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)

См. также

Другие абстрактные исполнители и формальные системы вычислений

Литература

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.

Полезное

Смотреть что такое «Машина Поста» в других словарях:

Машина Поста — математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит: из неограниченной в обе стороны ленты, разделенной на ячейки; из головка чтения/записи, которая может перемещаться вдоль ленты и управляется… … Финансовый словарь

Машина поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… … Википедия

Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна … Википедия

Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма … Википедия

поста́в — а, мн. постава, м. 1. только ед. ч. Манера держать в каком л. положении какую л. часть тела; постановка (чаще о голове). Был он строен, кряжист, с упругими мускулами и упрямым поставом головы. Гладков, Цемент. В них [оленях] все легко и прелестно … Малый академический словарь

ПОСТА МАШИНА — один из вариантов Тьюринга машины … Математическая энциклопедия

Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер … Википедия

Источник