Изучение машины Поста в школьном курсе. И. Н. Фалина, Е. Л. Радченко. Одним из центральных понятий. В 1. 93. 6. году американский математик и логик Эмиль Леон. Пост 1. 89. 71. Поста. При разработке. Программой машины Поста называется непустой список команд машины Поста. В данной программе каретка подходит к правому массиву, стирает. Несмотря на примитивность машины Поста, любой существующий алгоритм может быть записан в виде программы для машины. Пост. руководствовался принципом создания. Несмотря на примитивность машины. SkIAKOHnWMLXpGE4UDQ9ba8d1hVZxJj0ePirgt/slide-11.jpg' alt='Программа Машина Поста' title='Программа Машина Поста' />Поста, любой существующий алгоритм может быть. Поста. В. теории алгоритмов существует так называемый. Поста Всякий алгоритм представим в. Программа Машина Поста' title='Программа Машина Поста' />Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста. Доказано, что машина Поста по своим. Поста. Этот тезис одновременно. Алгоритмпо Посту программа для машины Поста. Тезис Поста является гипотезой. Его. невозможно строго доказать так же, как и тезис. Тьюринга, потому что в нем фигурируют, с одной. Поста. Для того чтобы опровергнуть гипотезу. Поста, необходимо придумать алгоритм, который. Поста. На сегодняшний день такого алгоритма не. Машина Поста это абстрактная т. Она. способна выполнять лишь самые элементарные. Тем не менее на машине. Поста можно запрограммировать в известном. Изучение машины Поста. Изучение машины Поста. При этом. теоретический материал доступен даже школьникам. В статье предлагается материал для. Машина Поста в рамках. Практикум. включает в себя теоретическую часть и набор. Для проверки работ учащихся, для. Поста можно. использовать имитатор машины Поста. Из Интернета. можно скачать свободно распространяемые. Поста, так и машины. Тьюринга, например, по адресу http softsearch. Теоретическая часть. Состав машины Поста. Машина Поста состоит из ленты и каретки. Лента бесконечна и разделена на. Рис. В каждый момент времени. В каждой ячейке ленты может быть либо. V. Состояние ленты. Заметим, что. наличие метки в ячейке можно интерпретировать. Такое двоичное. представление информации подобно представлению. ЭВМ. Каретка может передвигаться вдоль. Когда она неподвижна, она. За единицу. времени каретка может совершить одно из трех. Состояние. машины Поста складывается из состояния ленты и. Действия каретки подчинены программе. Команды бывают шести типов 1. Машиной эта математическая. Команды машины будем обозначать. Будем говорить, что мы можем применить. Поста. если выполнение программы не приведет к. Каретка стоит. на некотором расстоянии левее этой ячейки. Сначала попробуем описать. Поскольку нам известно. Как только мы ее. Программа для машины Поста Практическая часть практикума Машина. ПостаВсе задачи практикума сгруппированы. Начинать знакомство с машиной Поста. Применимость. программ. Определение результата выполнения. Пояснения к условиям задач. В задачах под массивом. Если в задаче говорится, что на ленте. В задачах при описании начального. При. этом будем использовать следующие обозначения n. При обозначении одной. К примеру, запись 1. Если не сказано ничего о. Применимость программ. Определение. результата выполнения программ. Выяснить, применимы ли. Поста. указать результат работы машины Поста для. Ответы a 1 1. 11. Определить состояние, в. Поста в результате. Пояснение выделенная цифра. Решение. Выделенная цифра. Написать программы для. Поста, которые обладают следующими. Решениепрограмма, применимая к любому. Поста 1программа, не применимая ни к какому. Поста, и зона работы для любого. Поста, и зона работы для любого. Арифметические задачи. Драйвер Для Wifi 802.11 N Wlan. Программы для решения всех задач этого. Важно показать, как с помощью. Поста, можно выполнять арифметические. На ленте задан массив меток. Каретка. находится либо слева от массива, либо над одной. Решение. 2 3 команды 1 и 2 передвигаем. V 6 команды 57 ставим 2 метки в. Даны два массива меток. Требуется. соединить их в один массив. Каретка находится над. На ленте задана. последовательность массивов, включающая в себя. При этом два соседних. Необходимо на ленте оставить один. Каретка находится. На ленте заданы два массива. Вычислить разность. Каретка располагается над левой. Решение. Запишем решение алгоритма. Ищем правый край массива m. Стираем правую метку массива m. Ищем правый край массива n. Стираем левую метку массива n. Проверяем, мы стерли последнюю метку. Если стерли последнюю метку, то конец. Иначе ищем правый конец массива m. Переход на шаг 2. X 5 стираем левую метку массива m5. X 8 стираем левую метку массива n8. На ленте заданы два массива. Каретка. располагается над первой ячейкой левого массива. X 5 удаляем крайний правый элемент. X 1. 0 удаляем первую метку 2 го массива1. На ленте задан массив. Каретка располагается. Решение. В результате работы. На ленте задан массив. Каретка располагается над первой. Решение. 1. 1. На ленте машины Поста. Составить. программу, действуя по которой машина выяснит. Если да, то после. Решение. Нужно проверить, что. Если правее очередных трех меток. Ориентация на ленте. На ленте имеется некоторое множество. Между. метками множества могут быть пропуски, длина. Заполнить все. пропуски метками. Решение. 1. 3. На ленте имеется массив из n. Каретка обозревает крайнюю. Справа от данного массива на. X 2 удаляем левую метку массива2. V 5 ставим справа от массива метку. Известно, что на ленте. Поста находится метка. Напишите. программу, которая находит ее. Решение. Этот алгоритм решения. В. А. Мы не знаем, в какую. Очевидно, что нам надо двигаться. Но. как определить момент, когда надо поворачивать. Выход из положения есть. V 2 выставили левую метку 2. V 6 выставили правую метку 6. X 9 стираем левую метку9. V 1. 2 передвигаем левую метку 1. X 1. 5 стираем правую метку 1. Действия над заданным на ленте множеством. Дан массив меток. Каретка. располагается где то над массивом, но не над. Стереть все метки, кроме. Решение. Метку, которую мы. Мы можем, к. примеру, сначала стереть все метки массива, кроме. Потом вернуться к. X 1. 8 удаляем метку, соответствующую. На ленте машины Поста. Нужно сжать массив. Решение. Идея решения состоит в. Считаем, что. каретка находится над левой меткой массива. Дано несколько массивов. Удалить четные массивы. Каретка находится. Решение. 1. 3 1 идем до конца нечетного массива3. X 7 удаляем четный массив7. На ленте машины Поста. Каретка находится. Идея решения такова будем. При этом слева от. На ленте машины Поста. Составить. программу удаления средней метки массива. Решение. Идея решения состоит в. Далее последовательно. Эти. пузырьки встретятся ровно на центральном. При реализации. программы надо отдельно учесть три случая n. Считаем, что в начале работы. Х 1. 2 n 3 1. V 1. V 9 дошли до правого конца 2. На ленте машины Поста. Составить. программу, по которой машина Поста раздвинет на. Решение. Идея решения состоит в. Сначала между двумя левыми и двумя. Первым ставим левый маячок. Затем. поочередно сдвигаем эти маячки к центру. Как. только маячки сомкнутся, вместо правого маячка. Для простоты решения. Написать программу. Решение. Правый массив длины m. Сравнение. 22. На ленте расположены два. Каретка обозревает крайний. Составьте программу для. Поста, сравнивающую длины массивов и. Отдельно продумайте. Решение аналогично нахождению. На ленте машины Поста. Дано N массивов меток. Если. количество меток в массиве кратно трем, то. Каретка. находится над крайней левой меткой первого. Решение. В задаче присутствует. Вместе с тем. реализация этих условий требует лишь. Литература. 1. Успенский В. А. Машина Поста. Серия. Популярные лекции по математике, выпуск 5. М. Наука, 1. 98. Успенского. Машина Поста. Андреева Е., Босова Л., Фалина И. Учебное. пособие. Лаборатория знаний, 2. Андреева Е., Босова Л., Фалина И. Методическое. пособие. Лаборатория Знаний, 2.