А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 10
Текст из файла (страница 10)
После первой единицы МТ чередует состояния. Если в слове чётноеколичество нулей, то состояние q2 — заключительное, иначе МТбесконечно будет сдвигаться вправо.IV.1.4(1– 2). Построить в алфавите {0, 1} машину Тьюринга, переводящую конфигурации K1 в конфигурации K0 :1) K1 = q1 1n , K0 = q0 1n 01n (n > 1);2) K1 = q1 0n 1n , K0 = q0 [01]n (n > 1).J1. МТ просматривает слово с первой непустой ячейки слева. Текущую единицу заменяет на ноль, двигается вправо до нуля, пропускает его и в первой пустой клетке печатает единицу, возвращаетсявлево, восстанавливает единицу, сдвигается вправо на следующую.Программу можно записать так:q1 0q6 0L,q1 1q2 0R,q2 1q2 1R,q2 0q3 0R,q3 1q3 1R,q3 0q4 1L,q4 1q4 1L,q4 0q5 0L,q5 1q5 1L,q5 0q1 1R,q6 1q6 1L,q6 0q0 0R.2. МТ просматривает слово с первой непустой ячейки слева. ЕслиМТ считывает нули, то каждый второй заменяет на единицу.
Кактолько была прочитана первая единица, МТ чётные единицы меняет на нули. Доходит до конца слова, переводит головку вперед.q1 0q2 0R,q2 0q1 1R,q1 1q3 0R,q3 1q4 1R,q4 1q3 0R,q2 1q4 1R,q4 0q5 0L,q5 1q6 1L,q6 0q5 0L,q5 0q0 0R.IV.1.5(1). Показать, что для всякой машины Тьюринга существуетэквивалентная ей машина, в программе которой отсутствует символ S.J Рассмотрим орграф, строящийся следующим образом: наличие команды qi αqj βS порождает наличие в графе вершин qi α и qj β и дуги88(qi α, qj β). В этом графе все вершины имеют полустепень исхода не более 1. Двигаясь по дугам из произвольной вершины, мы либо попадёмв контур, либо остановимся в некоторой вершине. В первом случае длявсех вершин заменим исходную команду на группу команд, организующих зацикливание, например, переход в новое состояние, в которомлюбой символ не меняется, а головка двигается вправо.
Во втором случае, пусть конечная вершина маршрута qk γ. При наличии команды видаqk γql δT , где T ∈ {R, L} команду qi αqj βS заменим на qi αql δT . При отсутствии такой команды, добавить состояние q 0 , заменить команду qi αqj βSна qi αq 0 γR и добавить всевозможные команды вида q 0 εqk εL, где в качестве ε берутся все буквы алфавита.IV.1.6. Показать, что для всякой машины Тьюринга T в алфавитеА существует счётно-бесконечное множество эквивалентных ей машинT1 , T2 , . .
. , Tm , . . . в том же алфавите А, отличающихся друг от другасвоими программами.J В качестве машины Tm можно рассмотреть МТ, при любом входесдвигающуюся влево на m позиций, затем сдвигающуюся вправо на mпозиций, и далее реализующую преобразования машины T .IV.1.8(1, 3, 4). По словесному описанию машины Тьюринга построитьеё программу в алфавите {0, 1}.1. Начав работу с последней единицы массива из единиц, машина«сдвигает» его на одну ячейку влево, не изменяя «остального содержимого» ленты.
Головка останавливается на первой единице«перенесённого» массива.3. Машина начинает работу с самой левой непустой ячейки и отыскивает единицу, примыкающую с левой стороны к первому слева массиву из трёх нулей («окаймлённому» единицами). Головкаостанавливается на найденной единице (если такая есть). Содержимое ленты не меняется.4. При заданном l > 1 головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается вправо до тех пор,пока не пройдёт подряд l + 1 нулей. Головка останавливается напервой ячейке за этими l + 1 нулями, напечатав в ней 1.
Остальноесодержимое ленты не меняется.J1. Программу МТ, выполняющей описанные действия, можно записать так:q1 1q2 0L,q2 1q2 1L,q2 0q0 1S.893. Программу соответствующей МТ можно записать так:q1 1q1 1R,q1 0q2 0R,q2 0q3 0R,q3 0q4 0R,q4 1q5 1L,q5 0q5 0L,q5 1q0 1S,q2 1q1 1R,q3 1q1 1R,q4 0q6 0R,q6 0q6 0R,q6 1q1 1R.4. Программу соответствующей МТ можно записать так:q1 1q1 1R,qi 0qi+1 0R, i = 1, l + 1,ql+2 0ql+3 1S,qi 1q1 1R, i = 1, l + 1.IЗанятие № 2.10Операции над машинами Тьюринга. Функции,вычислимые на машинах ТьюрингаV.1.9(1). Построить композицию T1 T2 машин Тьюринга T1 и T2 попаре состояний (q10 , q21 ) и найти результат применения композиции T1 T2к слову P (q20 — заключительное состояние машины T2 ):q11q12q21q22T1 : 0 q12 0R q10 1LT2 : 0 q22 1R q21 1R1 q12 1R q11 0R1 q21 0L q20 1Sa) P = 13 02 12 ;б) P = 14 01.J Композиция машин Тьюринга T1 и T2 по паре состояний (q10 , q21 ):q11 0q12 0R,q11 1q12 1R,q12 0q21 1L,q12 1q11 0R,q21 0q22 1R,q21 1q21 0L,Результат применения:а) T1 T2 не применима к 13 02 12 ;б) T1 T2 (14 01) = [10]2 02 12 .q22 0q21 1R,q22 1q20 1S.IV.1.10(1).
Найти результат применения итерации машины T по паресостояний (q0 , q1 ) к слову P (заключительными являются состояния q0и q00 , k > 1):90q1q2q3q4q50T : 0 q0 0S q4 0S q5 0S q4 1R q0 1L1 q2 0R q3 0R q1 0R ——a) P = 13k ;б) P = 13k+1 ;в) P = 13k+2 .Ja) Итерация по паре состояний (q0 , q1 ) не применима к P = 13k .б) Итерация машины Тьюринга T не применима к словам вида P =13k+1 .в) Результатом применения итераций по паре состояний (q0 , q1 ) ксловам вида P = 13k+2 (k > 1) является слово 1.IV.1.14(1, 2, 4, 9, 10). Построить машину Тьюринга, вычисляющуюфункцию f :0, если x = 0,1) f (x) = sg(x) =1, если x > 1;2) f (x) = sg(x) =1 − sg(x); 1, если x = 1,1= 0, если x > 2,4) f (x) =x не определено, если x = 0;0, если x 6 y,· y=9) f (x, y) = x −x − y, если x > y;10) f (x, y) = x − y.J1.
Машина Тьюринга T выполняет следующие преобразования:T (1) = 1, T (1k ) = 12 , k > 2.q1 1q2 1R,q2 1q3 1R,q3 1q3 0R,q3 0q4 0L,q4 0q4 0L,q4 1q0 1L,q2 0q0 0L.2. Можно построить машину можно построить МТ как композициюМТ из первого пункта и МТ, изменяющей результат:q1 1q2 1R,q2 0q0 1L,q2 1q0 0S.4. Машина Тьюринга T выполняет следующие преобразования слов:T (1) = N aN, T (12 ) = 12 , T (1k ) = 1, k > 2.91q1 1q2 1R,q2 1q3 1R,q3 0q4 0L,q4 1q0 1L,q2 0q2 0S,q3 1q5 1R,q5 1q5 1R,q5 0q6 0L,q6 1q6 0L,q6 0q0 1S.9. Машина Тьюринга T выполняет следующие преобразования слов:(1,если x 6 y,T (1x+1 , 1y+1 ) =1x−y+1 , если x > y.Если x > 0 и y > 0, то МТ стирает по одной единице в их записи иначинает проверку заново. Если x > 0 и y = 0 или x = 0 и y > 0,то МТ стирает запись y и останавливается.y = 0, стираем запись y:q8 1q0 0S,y > 0, стираем 1 в x, y:q7 1q7 1R,q7 0q9 0L,q9 1q10 0L,q10 1q10 1L,q10 0q11 0L,q11 1q11 1L,q11 0q12 0R,q12 1q1 0R.q1 1q2 1R,q2 1q3 1R, тогда x > 0.q2 0q4 0R, тогда x = 0.x = 0, стираем запись y:q4 1q4 0R,q4 0q0 0S,x > 0, проверяем y:q3 1q3 1R,q3 0q5 0R,q5 1q6 1R,q6 1q7 1R, тогда y > 0.q6 0q8 0L, тогда y = 0.10.
Машина Тьюринга T выполняет следующие преобразования слов:если x = y, 0,если x > y,T (1x+1 , 1y+1 ) = x − y + 1, не применима, если x < y.Алгоритм аналогичен приведенному в предыдущем пункте. В случае x = 0 и y > 0 МТ зацикливается.q1 1q2 1R,q2 1q3 1R, тогда x > 0.q2 0q4 0R, тогда x = 0.x = 0, проверяем y:q4 1q5 1R,q5 1q5 1S, цикл, так как y > 0.92q5 0q6 0L, тогда y = 0.x = 0, y = 0, стираем y:q6 1q6 0L,x > 0, проверяем y:q3 1q3 1R,q3 0q7 0R,q7 1q8 1R,q8 1q9 1R, тогда y > 0.q8 0q10 0L, тогда y = 0.y = 0, стираем запись y:q10 1q0 0S.y > 0, стираем 1 в x, y:q9 1q9 1R,q9 0q11 0L,q11 1q12 0L,q12 1q12 1L,q12 0q13 0L,q13 1q13 1L,q13 0q14 0R,q14 1q1 0R.IV.1.15(2, 7). Построить машину Тьюринга, правильно вычисляющую функцию f :1;2) f (x) =x−32+x7) f (x, y) =.2−yJ2.
Машина Тьюринга T выполняет следующие преобразования слов: 1,T (1x+1 ) = 12 ,не применима,если x + 1 > 5,если x + 1 = 5,если x + 1 < 5.МТ проверяет условие x + 1 > 5, если оно не выполнено, то зацикливается; если же выполнено, то МТ стирает лишние единицы изисходного слова на ленте для записи ответа.q1 1q2 0R, тогда x + 1 > 1q2 1q3 0R, тогда x + 1 > 2q2 0q2 0S, цикл, x + 1 < 5q3 1q4 0R, тогда x + 1 > 2q3 0q3 0S, цикл, x + 1 < 5q4 1q5 0R, тогда x + 1 > 3q4 0q4 0S, цикл, x + 1 < 5q5 1q6 1R, тогда x + 1 > 4q5 0q5 0S, цикл, x + 1 < 5q6 0q0 1R, тогда x + 1 = 5q6 1q7 1R, тогда x + 1 > 5x + 1 > 5, сдвигаемся в конец слова, стираем всё, кроме левой единицы:q7 1q7 1R,q7 0q8 0L,q8 1q8 0L,q8 0q0 1S.937. Машина Тьюринга T выполняет следующие преобразования слов: x+22 +1 ,если y = 0,1T (1x+1 , 1y+1 ) =1x+3 ,если y = 1, не применима,если y = 1k , k > 1.МТ проверяет условие y 6 1, если оно не выполнено, то зацикливается; если выполнено, то реализует соответствующую функцию.Считаем, что числа x и y на ленте записаны корректно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
