Как удвоить массив в машине поста

Арифметически задачи, машина поста Информатика и ИКТ 10 класс

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

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

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

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

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

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

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

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

Источник

Задачи по машине Поста

Главная > Документ

Задачи по машине Поста

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

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

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

Составить программу нахождения разности двух целых неотрицательных чисел a и b. Если a меньше b, то перед разностью через одну пустую ячейку поставить метку. Каретка находится над крайней левой меткой левого числа.

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

Дано N массивов меток. После последнего массива на расстоянии более трёх пустых ячеек находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массиве >=2. Если количество меток в массиве кратно трём, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

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

Написать длину слова целым без знака.

Задачи по машине Тьюринга

На ленте машины Тьюринга записан массив из N штук звёздочек («*»). Задание: если N>5, то вывести N-2; если N=5, то вывести 1; если N Алгоритм Маркова

Задача 1: Дана последовательность скобок. С помощью нормальной системы подстановок Маркова определите правильность скобочной структуры.

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

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

Задача 4: Напишите программу, автоматически реализующий нормальный алгоритм Маркова, умножающий два числа.

Задача 5: Задана строка из больших букв английского алфавита (символы от A до Z)), заканчивающаяся знаком вопроса «?». Надо написать набор правил, который отсортирует её по возрастанию и выведет без знака вопроса. В отсортированном виде DFAAS? будет выглядеть как AADFS.

Задача 6: Дано двоичное число. Предложите систему нормальных подстановок, которая инвертирует все 0 и 1.

Источник

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

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

Одним из центральных понятий информатики является понятие алгоритма. В 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 массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

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

Источник

Лабораторная работа №13 Тема: «Разработка программ для машины Поста»

Лабораторная работа №13

Тема: «Разработка программ для машины Поста»

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

Теоретическая часть:

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

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

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

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

Система команд Машины Поста

Практическая часть

Задание №1 Выполнить задачи, используя эмулятор Поста

Вариант №1

Вариант №2

Вариант №3

Вариант 4

Задание 2. Ответить на контрольные вопросы.

1.Какие действия допустимы для каретки в машине Поста? Тьюринга?

3. Объясните порядок работы машины Поста.

3. Что представляет собой таблица машины Поста?

4. Напишите команду «Записать метку», «Снять метку » в эмуляторе.

5.Как остановить программу в эмуляторе?

Задание 3. Сделать вывод о проделанной работе.

Источник

Программирование на машине Поста

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

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

Пример

Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):

Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

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

Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.

P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.

Источник