Написать программу для машины тьюринга
Написать программу для машины тьюринга
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «
Машина Тьюринга на шаблонах
Каждый интересующийся шаблонами в С++ скорее всего слышал об их Тьюринг-полноте и связанных с этим шутках про «we put a language in your language, so you can program while you program». В этом посте я расскажу как с помощью шаблонов и константных выражений построить настоящую машину Тьюринга, вычисляющую результат своей работы во время компиляции, на которой можно будет запускать уже существующие программы. Например усердный бобер с 4 состояниями и 2 символами выглядит как-то так:
На выходе, как и положено, получаем
Тут можно посмотреть на код: https://ideone.com/MvBU3Z. Желающие узнать как все устроено внутри, добро пожаловать под кат.
Для полноценной работы машины Тьюринга (МТ далее) нужно следующее:
1. Лента с символами
2. Способ считывать и записывать символы на ленту
3. Способ перемещаться по ленте и расширять ее по мере надобности
4. Система состояний и правил перехода
5. Способ вычислять следующее состояние системы целиком (машина + лента)
6. Способ останавливать выполнение, когда машина достигает финального состояния
Все операции должны выполняться над типами и константными выражениями, а не над переменными как в обычной жизни. Для согласованности со стандартной библиотекой С++, мы будем использовать следующий способ вычислений:
Использование имени «type» для хранения результатов сделает возможным некоторые полезные трюки с std::conditional и std::integral_constant, которые мы увидим в далнейшем.
Что можно сделать с лентой? Можно ее, например, вывести на экран. Функция print будет единственной функцией в обычном понимании, которая будет использоваться в программах для нашей машины.
Здесь используется стандартный трюк с рекурсивным шаблоном. По ссылке можно посмотреть на получившийся код: https://ideone.com/DBHSC6
2. Прежде чем перейти к чтению и записи, необходимо сделать некоторые вспомогательные операции:
С конкатенацией все просто.
Инверсия чуть-чуть посложнее: берем первый символ, переносим его в конец и конкатенируем с перевернутым хвостом. Внутри разворачивается рекурсия в результате которой получается то, что нам нужно. Вот пример запуска: https://ideone.com/47GKNp
Чтение символов — место, где начинается магия со стандартной библиотекой.
Логика на самом деле относительно проста: если n == 0, мы возвращаем первый символ ленты, обернутый в std::integral_constant, в противном случае мы уменьшаем n на единицу и отбрасываем первый символ. Для чего нужна конструкция ::type::type? Первый type относится к std::conditional. std::conditional ::type равняется A, если T == true, и равняется B в остальных случаях. Таким образом, в зависимости от значения n, вся конструкция развернется в одно из следующих выражений:
Разгадка: в первом случае шаблон Read > будет инстанциирован в зависимости от значения n, во втором он будет инстанциирован всегда, так как мы явно используем внутренний alias (::type). Если мы всего лишь упомянем имя шаблона, он не будет инстанциирован, если мы попытаемся использовать что-то из его внутренностей, шаблон будет инстанциирован. Таким образом, выражение из второго примера приведет к бесконечной рекурсии, которая все же остановится, но с ошибкой. Этот примем с ::type::type будет активно использоваться в дальнейшем.
Тут можно посмотреть на пример чтения с ленты: https://ideone.com/vEyASt
Запись. Допустим мы хотим записать на ленту вместо символа х символ y. Операцию записи можно представить как деление всей ленты на часть до х, сам символ х и часть после х, замену x на y и конкатенирование всех частей обратно в целое. Определим операции для вычисления n первых и последних символов:
Чтобы получить n последних символов, будем делать примерно то же, что делали для чтения: укорачивать ленту по одному символу, пока длина оставшегося куска не станет равна n. Чтобы получить первые n символов, перевернем ленту, возьмем последние n символов и перевернем результат. Примеры использования: https://ideone.com/igYF3W.
Наконец, непосредственно запись:
Этот код не сложно понять, зная, что тут на самом деле происходит. Примеры записи: https://ideone.com/w2mUdh
В данный момент мы имеем класс для представления ленты, а также умеем читать и писать символы. Теперь нужно научиться двигать ленту.
3. Наша МТ будет поддерживать следующие операции передвижения: Hold, Left and Right. Каждая из них должна уметь вычислять следующую позицию и следующее состояние ленты, зная текущее ее состояние и позицию. Если машина смотрит на символ в позиции 0 и мы хотим сдвинуть ее влево, ленту необходимо расширить. Аналогично в случае, когда машина смотрит на конечный символ и двигается вправо.
4. Теперь можно переходить к состояниям. Если машина находится в каком-то состоянии и читает символ с ленты, нам нужно знать три вещи: что писать, куда двигаться и в какое состояние перейти. Состояния решено было запрограммировать как группу специализаций шаблонов, где каждая специализация соответствует паре (состояние, символ), то есть правилу перехода. Предположим, мы хотим задать следующее правило: находясь в состоянии A и прочитав символ 0, нужно записать вместо него 1, сдвинуться вправо и перейти в состояние B. Выглядеть это правило будет вот так:
Здесь использована отличная возможность современного С++: alias template. Поля «move» и «next» не просто типы, а шаблоны типов, в дальнейшем они будут использованы МТ для вычисления своего следующего состояния. Писать такую конструкцию для каждого правила довольно утомительно, поэтому обернем задание правил перехода в макрос. Состояние, перейдя в которое машина должна остановиться, назовем Stop.
5. Чтобы удерживать состояние всей системы (состояние машины, ее текущая позиция и состояние ленты), определим класс Machine. Единственное, что должен уметь этот класс — делать один шаг симуляции, вычислять свое следующее состояние.
Сперва мы считываем символ с ленты и сохраняем его как «symbol». Далее мы инстанциируем класс State с конкретным значением символа и получаем правило перехода. Следующее состояние машины определяется следующим образом:
Зачем нужно ключевое слово «template» перед «next»? Согласно стандарту, перед именем вложенного шаблона необходимо писать «template», если это имя используется после оператора разрешения области видимости(«::»). При вычислении операции перемещения можно наблюдать тот же эффект.
Чтобы вычислить следующее состояние ленты, запишем в нее новый символ и по необходимости расширим, последовательно вызвав операции записи и перемещения. Вычисление новой позиции очевидно.
Наконец, все готово, и мы умеем вычислять следующее состояние системы, делать шаги. Можно написать временную вспомогательную функцию для вывода состояния машины, придумать какую-нибудь простую программу и пошагово следить за ее выполнением: https://ideone.com/XuBDry. В этом примере можно наблюдать, как машина движется право и заменяет все на своем пути.
6. Все выглядит так, как будто работает, но мы должны идти глубже: входными данными для процесса являются начальное состояние машины, ее позиция и состояние ленты, в конце мы хотим знать только что случилось с лентой, когда машина достигла состояния Stop. Окей, напишем класс
Чтобы проверить условие остановки, мы инстанциируем текущее состояние машины и состояние Stop со значением 0, после чего сравниваем их между собой посредством std::is_same. Если они равны, возвращаем ленту, в противном случае делам следующий шаг и снова проверяем условие остановки.
Попробуем теперь написать что-нибудь. Например увеличение чисел в бинарном формате. Предположим, что число записано слева направо, как на бумажке.
Решение задач. Машина Тьюринга
Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.
Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.
Перенести первый символ непустого слова P в его конец. Алфавит : A=
Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.
Для решения этой задачи предлагается выполнить следующие действия:
В противном случае уничтожить всё входное слово ( q 7 ).
Запомнить первый символ, стереть второй символ и установить на его месте первый.
Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q 1 ) или c (если в q 2 ), переходим вправо и меняем состояние на q 1 (если в текущей клетке было записано b ) или на q 2 (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.
После этого возвращаемся к началу входного слова.
Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.
Написать программу для машины тьюринга
Абстрактные вычислительные машины
Материал взят с ресурса Планета информатики
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).
Материал взят с ресурса Планета информатики
Решение этой задачи аналогично рассмотренному выше примеру.
Задача 4 (усложнение задачи 3)
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
Рассмотрим следующие варианты входных слов:
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
После программы запуска возможны варианты:
Эмулятор машины Тьюринга
Как пользоваться эмулятором
Что такое машина Тьюринга?
Машина Тьюринга — абстрактная вычислительная машина, предложенная Аланом Тьюрингом для формализации понятия алгоритма. Устройство МТ состоит из следующий частей:
Бесконечная лента
Обычно на ленту в начале работы помещают входное слово. В процессе работы машины Тьюринга содержимое ленты модифицируется устройством управления и в результате на ленте остаётся выходное слово.
Считывающая/записывающая головка
В каждой машине Тьюринга есть специальная головка, указывающая на одну определённую ячейку на ленте. Данное устройство позволяет считывать символ с ячейки, над которой находится, или записывать символ в эту ячейку. Также головка может перемещаться влево и вправо на одну ячейку, или оставаться на месте.
Устройство управления
Допускаются краткие записи для правил:
Примеры машин Тьюринга
Пример 1 (загрузить в эмулятор). К двоичному числу прибавить 1. В начальный и конечный момент головка должна находиться на самом старшем бите слова (слева).
Так как изначально по условию головка МТ находится на самом старшем бите, а увеличивать надо младший, необходимо сначала переместить головку на младший бит, что выполняется в состоянии q0: как только лента увидит символ λ, она сдвинется влево (на младший бит) и перейдёт в состояние икремента (q1).
В состоянии q1 возможны следующие ситуации:
Состояние q2 нужно лишь для выполнения условия остановки головки на старшем бите. Оно полностью аналогично начальному состоянию, только движение происходит в левюу сторону и при достижении пустого символа головка сдвигается вправо и выполняется останов.
Пример 2 (загрузить в эмулятор). В слове из алфавита
| Q \ A | a | b | λ |
|---|---|---|---|
| q0 | b R q0 | a R q0 | ! |
Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.