Решение задач. Машина Тьюринга

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

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

Перенести первый символ непустого слова P в его конец. Алфавит : A=.

Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.

Если первый и последний символы (непустого) слова P одинаковы, тогда это слово не менять, а иначе заменить его пустым словом. Алфавит: A =< a , b , c >.

Для решения этой задачи предлагается выполнить следующие действия:

Запомнить первый символ входного слова, не стирая его (перейти в состояние q ₁ , если первый символ – a , q ₃ , если первый символ – b и q ₅ , если первый символ – c ).

Переместить автомат под последний символ и сравнить его с запомненным (в q ₂ для a , в q ₄ для b и в q ₆ для c ). Если они равны, то больше ничего не делать.

В противном случае уничтожить всё входное слово ( q ₇ ).

Удалить из слова P его второй символ, если такой есть. Алфавит: A =< a , b >.

Запомнить первый символ, стереть второй символ и установить на его месте первый.

Удалить из слова P первое вхождение символа a , если такое есть. Алфавит : A=.

Если первый символ слова – a , то стереть его и остановиться. Иначе сдвигаем символы слова на один символ вправо до тех пор, пока не найдем символ a .

Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q ₁ ) или c (если в q ₂ ), переходим вправо и меняем состояние на q ₁ (если в текущей клетке было записано b ) или на q ₂ (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.

Если P — непустое слово, то за его первым символом вставить символ a . Алфавит: A = < a , b , c >.

Аналогично заданию 5 запоминаем первый символ слова, меняем его на символ a , переходим на одну клетку влево и ставим там этот символ.

Вставить в слово P символ a за первым символом c , если такое есть. Алфавит: A = < a , b , c >.

Просматриваем слово до символа c или пустой клетки (в последнем случае останавливаем программу сразу). Затем, если c найден, запоминаем его и меняем на символ a , а далее запускаем цикл, который справа налево сдвигает символы слова, первоначально вставляя символ c перед a .

Удалить из P все вхождения символа a . A = < a , b , c >.

Вместо сдвига символов слова для закрытия образующихся дырок можно построить новое слово справа от предыдущего. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком = , отличным от всех символов алфавита A .

Идем в конец слова и ставим знак = .

После этого возвращаемся к началу входного слова.

Теперь наша задача – перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово. Для этого анализируем первый символ входного слова. Если это a , тогда стираем его и переходим к следующему символу. Если же первый символ – это b или c , тогда стираем его и «бежим» вправо до первой пустой клетки, куда и записываем этот символ. Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу.

Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак = . Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a , в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться.

Удвоить слово P , поставив между ним и его копией знак = . Алфавит: A = < a , b >.

Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.

Далее заменяем видимый символ a на двойник A (чтобы при возвращении к исходному слову знать, с какого символа продолжать копирование), «бежим» вправо до первой свободной клетки и записываем в неё символ a . После этого возвращаемся влево к клетке с двойником A , восстанавливаем прежний символ a и сдвигаемся вправо к следующему символу. Теперь аналогичным образом копируем второй символ (заменяем его на A , в конец дописываем a и т.д.) и все последующие символы входного слова.

Когда мы скопируем последний символ входного слова и вернёмся к его двойнику, то затем после сдвига на одну позицию вправо мы попадём на знак = . Это сигнал о том, что входное слово полностью скопировано, поэтому останавливаем программу.