Написать программу машины тьюринга переводящую конфигурацию

Содержание

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разбитой на ячейки, и рабочей головки. Она работает в дискретные моменты времени: t0, t1, …, tn, … В каждый момент во всякой ячейке ленты может быть записана одна из букв некоторого конечного внешнего алфавита A = < a0, a1, … ak-1>, а головка может находиться в одном из конечного числа внутренних состояний
Q = 0,q1,…qr-1>- внутренний алфавит. Символ a0является «пустым» (будем обозначать его L) и что все клетки ленты заполнены этим символом.

В каждый момент времени рабочая головка обозревает одну ячейку ленты и выполняет следующие действия:

1) заменяет символ в обозреваемой ячейке новым (возможно, прежним);

2) переходит в новое состояние (возможно, в прежнее);

3) сдвигается на одну ячейку (вправо R или влево L ) либо остается на месте H.

Совокупность команд будем называть программой машины Тьюринга.

Среди состояний машины (головки) выделено одно, называемое заключительным (впредь мы будем считать, что это состояние q0).

Как запрограммировать на машине Тьюринга сложение? Душкин объяснит

Под конфигурацией машины Тьюринга мы понимаем распределение букв алфавита А по ячейкам ленты, состояние головки и обозреваемую ячейку. Работа машины Тьюринга по программе состоит в смене конфигураций. Конфигурацию в момент времени ti будем обозначать K ti. Если эта конфигурация не является заключительной, то машина в соответствии со следующей командой переходит в конфигурацию K ti+1.

Если нужно решить некоторую задачу на машине Тьюринга, исходным данным задачи сопоставляется начальная конфигурация K t0, а ответ задачи определяется заключительной конфигурацией, в которую программа машины переводит конфигурацию K t0.

1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите .

Решение: внешний алфавит машины будет следующим: < L, 0, 1 >.

Будем считать начальной следующую конфигурацию: Lq1s1…spL. Для того, чтобы прибавить 1 к двоичному числу n сначала необходимо «отогнать» головку машины вправо и установить ее под последней (самой младшей) цифрой двоичного числа. Если последняя цифра числа есть 0, то достаточно заменить 0 на 1 и завершить процесс, то есть перевести головку (машину) в заключительное состояние q0.

Если же последняя цифра числа есть 1, то необходимо заменить ее на 0, а головку сдвинуть влево, чтобы «увидеть» следующий разряд двоичного числа. Если окажется, что этот разряд содержит 0, то заменить 0 на 1 и опять-таки перевести головку (машину) в заключительное состояние q0. Если же этот разряд содержит 1, необходимо заменить ее на 0 и опять сдвинуть головку влево. И так далее, до тех пор, пока либо не встретится разряд, содержащий 0, либо головка дойдет до первого слева пустого символа L. В любом из этих случаев 0 или L следует заменить на 1 и перевести головку (машину) в заключительное состояние q0.

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

Конструирование машины Тьюринга

q11 ®q11R q10 ®q10R q1L ®q2LL q20 ®q31H q21 ®q20L

q2L ®q01H q31 ®q31L q30 ®q30L q3L ®q0LR.

2. Пусть требуется перевести запись натурального числа n, изображенного в виде последовательности n «палочек» (|) n ³ 1, в двоичную запись в алфавите . Т.е. конфигурация Lq1…|L должна быть преобразована в Lq0s1s2…sp L, где s1s2…sp — двоичная запись n.

Решение: в качестве внешнего алфавита машины берем алфавит:< L, |, 0,1 >.

Опишем алгоритм решения задачи в словесной форме:

1. «Отогнать» головку машины влево до первого пустого символа, заменить этот символ нулем (0).

2. «Отогнать» головку машины вправо до последней черточки, заменить ее пустым символом. Запомнить, что 1 из унарного представления числа n вычтена.

Алгоритмы: машины Тьюринга

Машину Тьюринга Phi будем называть распознающей, если для некоторого алфавита Sigma и каждого входа x in Sigma ^<*> , на котором Phi останавливается, ее результат < Phi >(x) in < 0, 1> , т.е. Phi вычисляет некоторую двузначную функцию (возможно частичную) на словах из Sigma.

Лемма 9.5. Пусть Phi — распознающая м.Т ., м.Т . <cal M>_1 вычисляет функцию f(x) , а м.Т . <cal M>_2 — функцию g(x) . Тогда существует м.Т . cal M, вычисляющая функцию

h(x) =left< begin f(x) при > mbox < при > Phi >(x)*x . Выбор между f и g происходит по следующим командам :

p 0 rightarrow p_0 wedge textit< П >; p1 rightarrow p_1 wedge textit< П>; p_0* rightarrow q_0^1 wedge textit< П>; p_1* rightarrow q_0^2 wedge textit< П>

Кроме того, обеспечим переход в новое заключительное состояние:

q_f^1 a rightarrow q_f a textit< Н >; q_f^2 a rightarrow q_f a textit< Н> (a in Sigma ).

Таким образом, мы реализовали в терминах машин Тьюринга обычный в языках программирования оператор ветвления :

mbox <bf if > Phi(x)=0 mbox f(x) mbox g(x) mbox .

Повторение (цикл)

Используя конструкцию для ветвления легко реализовать в терминах машин Тьюринга и оператор цикла .

Лемма 9.6. Пусть Phi — распознающая м.Т ., а м.Т . <cal M>_1 вычисляет функцию f(x) . Тогда существует м.Т . cal N, которая вычисляет функцию, задаваемую выражением:

g(x) =

Доказательство. Действительно, пусть м.Т . — вычисляет тождественную функцию g(x)=x . Построим по м.Т . Phi, _1 mbox < и > _2 м.Т . cal M, реализующую ветвление как в лемме 9.5. Тогда искомая м.Т . cal N получается из cal M заменой команд q_^ a to q_ a H (a in Sigma ) на соответствующие команды , обеспечивающие зацикливание.

Реализованные выше операции над машинами Тьюринга и вычислимыми функциями позволяют получать программы новых м.Т ., используя обычные конструкции языка программирования «высокого» уровня: последовательную и параллельную композицию , ветвление и цикл . Пусть M, M_<1>, M_,dots , M_, Phi

— машины Тьюринга . Последовательную композицию M1 и M2 будем обозначать M1;M2 , параллельную композицию M1, M2. , Mm обозначаем как mathbf <par>_b(M_1,M_2,ldots , M_m)

(здесь b — это символ, разделяющий аргументы и результаты этих машин), ветвление —

Задачи

Sigma.

Задача 9.1. Постройте м.Т . для функции копирования , не увеличивая исходный алфавит

Задача 9.2. Постройте программу м.Т ., которая выполняла бы перенос непустого слова в заданное место ленты , т.е. для любого слова w in (Sigma setminus < wedge >)^ и n > 0 выполняла преобразование конфигураций : q_1w wedge^n # vdash^* wedge^n q_2#w .

<cal M>Задача 9.3. Достройте программу м.Т . ^prime из леммы 9.1 на этапах 3 и 4.

Задача 9.4. Докажите, что односторонняя м.Т . <cal M>^prime, построенная в лемме 9.2, корректно моделирует исходную м.Т . <cal M> .

Задача 9.5. Другой, по сравнению с конструкцией леммы 9.2, подход к моделированию двухсторонней ленты на односторонней заключается в том, чтобы содержимое правой полуленты cal M хранить в четных ячейках cal M^prime, а содержимое левой полуленты — в нечетных, поместив в 1-ю ячейку специальный маркер. Постройте программу , реализующую этот подход (ее достоинство — увеличение алфавита ленты всего на 1 символ).

cal M

Задача 9.6. Достройте программу м.Т . из леммы 9.4 на этапах 1, 3 и 5.

Задача 9.7. Построить программы машин Тьюринга , вычисляющих следующие функции.

Перевод из двоичной системы в унарную: f bu (n(2))= | n .
Сложение и вычитание в двоичной системе: sum(n*m)=n+m и совпадает с — при n >= m и при m > n ).
Умножение в двоичной системе: mul(n*m)= n x m . ( Реализуйте алгоритм умножения «в столбик».)
Возведение в степень: exp(n*m)= n m .
Извлечение квадратного корня: .
Логарифмирование: .
Деление: $div(n*m) =lfloor frac<n>< m>rfloor (m neq 0)$ .
Остаток от деления: rest(n*m) = n mod m .
Функция выбора аргумента: .

Задача 9.8. Используя машины Тьюринга из предыдущей задачи, построить программы машин Тьюринга , вычисляющих следующие функции.

$begin f_1(x, y) left x^2y^3, если > x < y \ lfloor (x+y)/2 rfloor , в противном случае>end right. \ end$

$begin f_2(x, y)left lfloor sqrt rfloor , если >x+1 geq y \ 2(x +y), в противном случае>end right. \ end$

$begin f_3(x, y)left lfloor log_2 (1+ lfloor frac < y>rfloor) rfloor, если >x > 2 y\ xy, в противном случае>end right. \ end$

$begin f(x, y)left lfloor sqrt rfloor , если >2x geq y \ (x mod y), в противном случае>end right. \ end$

Задача 9.9. Докажите, что всякую арифметическую функцию f(x) , вычислимую на некоторой м. Т. M = <Q, Sigma , P,q_<0>, q_> , можно также вычислить на м. Т. M’ ,, алфавит ленты которой содержит лишь два символа wedge и | . (Указание: используйте для моделирования одного символа из Sigma блок из нескольких подряд идущих ячеек, содержащих его код в алфавите < wedge , , | > ) и замените каждую команду M группой команд, обрабатывающих соответствующий блок ячеек).

Задача 9.10. Построить машину Тьюринга , определяющую по слову x в алфавите симметрично ли оно, т. е. вычисляющую функцию:

$f(x) = left <begin 1, если слово x симметрично>\ 2, в противном случае>end right.$

x prec y Leftrightarrow exists i leq n [(x_1=y_1) ldots (x_Задача 9.11. Построить машину Тьюринга , сравнивающую два слова x=x1x2. xn и y=y1y2. ym в алфавите лексикографически: =y_) y_i )] или для некоторого непустого слова x’ выполнено y = x x’ . Эта машина Тьюринга должна вычислять функцию:

$f(x, y) = left <begin 1 , если $x prec y$ >\ 2 , если $x = y$ >\ 3 , если $y prec x$ >end right.$

Источник: intuit.ru

Тьюрингово программирование

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

Назовем заключительную конфигурацию стандартной, если в ней головка наблюдает первый значащий символ результата, который находится в 1-ой ячейке (т.е. в той же ячейке, где начиналось входное слово).

1. Построить машину Тьюринга, переводящую слово в слово , если внешний алфавит .

2. Проверить работу машины Тьюринга над некоторым словом.

1. Опишем работу алгоритма, решающего задачу.

Будем обозначать состояния машины Тьюринга числами 0,1,2,…, причем 1 ‑ начальное, а 0 ‑ заключительное состояния.

Так как нам надо переписать слово в обратном порядке, то понадобится вспомогательный символ внешнего алфавита, который обозначим «*», т.е. .

Вначале с помощью команд ; заменяем на «*» и движемся влево. Признаком окончания слова будет считывание λ в состояниях 2 или 3. С помощью команд

печатаем символ , движемся вправо и переходим в состояние 4.

Запишем промежуточные конфигурации:

Если в состоянии 4 считываем символы а или b, то, не изменяя символы и состояние, движемся вправо. Это позволит пройти новое слово, которое строим, без изменений.

Если в состоянии 4 считываем символ «*», то это значит, что новое слово пройдено и надо переходить в следующее состояние 5, чтобы дойти до остатков старого слова.

Если в состоянии 5 считываем символ «*», то движемся вправо, не меняя символ и состояние. Если в состоянии 5 считываем символы а или b, значит, дошли до остатков старого слова. Заменяем символы на «*», переходим в состояния 2 или 3 и движемся влево.

, ,

В состояниях 2 или 3, двигаясь влево, нужно пройти все символы «*», а также новое слово. Это позволят сделать команды:

, , ,

, , .

Признаком того, что все символы «*», а также новое слово пройдены, будет считывание λ в состояниях 2 или 3.

Запишем промежуточные конфигурации:

Дальше по циклу все символы перепишутся. Признаком того, что старое слово закончилось, является считывание символа λ в состоянии 5. Остается стереть все символы «*» и остановится в начале нового слова. Для этого понадобятся команды:

; ; ; ; .

Запишем все конфигурации:

Программу найденной машины Тьюринга представим таблицей

AQ
λ	‑	‑
a
b
*	‑

2. Проверим работу машины Тьюринга над словом .

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

1. Построить машину Тьюринга, вычисляющую числовую функцию .

2. Проверить работу построенной машины над некоторым набором значений.

1. Будем обозначать состояния машины Тьюринга причем ‑ начальное, а ‑ заключительное состояния.

Набор значений аргументов изображается словом .

Аргумент должен остаться без изменения, этого можно добиться с помощью команды . Когда в состоянии встретиться символ λ, значит, мы попали на символ, разделяющий изображения аргументов, переходим в состояние , а сам символ λ пока оставим без изменений с помощью команды .

Далее набор единиц, изображающих аргумент , проходим до конца. Для этого добавим команды: ; .

Теперь с помощью «челночного» алгоритма удвоим количество единиц в блоке, изображающем вторую переменную.

Расширим алфавит, введя символ «*», т.е. . Будем заменять единицы блока метками «*» следующим образом.

Получили машину Тьюринга с внешним алфавитом , алфавитом внутренних состояний и программой, записанной в виде следующей таблицы:

AQ
λ					‑	‑	‑

*	‑	‑	‑	‑	‑	‑	‑

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