1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 22
Текст из файла (страница 22)
. . Это означает,что, находясь в состоянии qi и обозревая на ленте символ aj , машина может выполнить любую из этих команд. Если же в состоянии qi , обозревая символ aj , машинане находит в программе команду вида qi aj → . . ., то дальнейшие шаги в данной ветви вычислений невозможны. Таким образом, шаг работы машины уже не определеноднозначно, а процесс вычисления можно представлять как дерево конфигураций, вкотором из одной конфигурации может получиться уже несколько других.
Каждаяветвь дерева конфигураций либо является бесконечной, либо заканчивается в заключительном состоянии, либо обрывается на некотором незаключительном состоянии.В последнем случае мы будем говорить, что произошла неправильная остановка машины.Перейдем к формальным определениям.Определение. Недетерминированная машина Тьюринга — это упорядоченная пятерка T = hA, Q, P, q1 , q0 i, где A, Q, q1 , q0 имеют тот же смысл, что и у детерминированных машин, а программой называется любое подмножествоP ⊆ (Q \ {q0 }) × A × Q × A × {Λ, R, L}.Как и раньше, элементы программы P называются командами, и каждую командуhqi , aj , qk , al , Si ∈ P мы записываем в виде слова qi aj → qk al S.90Глава V. Теория сложности алгоритмовЗамечание.
Таким образом, в программе P недетерминированной машины для любых qi и aj может быть несколько команд вида qi aj → . . . Допускается также случай,когда в P команды, начинающиеся на qi aj → . . ., отсутствуют. Если в программе длялюбого qi (i > 0) и любого aj существует ровно одна команда вида qi aj → . . ., томашина T детерминирована.Конфигурации (машинные слова) для недетерминированных машин Тьюрингаопределяются так же, как и раньше. Переопределим отношение преобразования конфигураций за один шаг работы машины Тьюринга в недетерминированном случае.Определение. Пусть M = Aqi aj B — конфигурация недетерминированной машиныT .
Говорят, что конфигурация M 0 получается из M за один шаг работы машины T ,и пишут M `T M 0 , если выполняется одно из условий:а) В программе P существует команда вида qi aj → qk al , и M 0 = Aqk al B.б) В программе P существует команда вида qi aj → qk al R, B = as B 0 , и M 0 =Aal qk as B 0 .в) В программе P существует команда вида qi aj → qk al R, B = Λ, и M 0 = Aal qk a0(достраивается новая ячейка справа).г) В программе P существует команда вида qi aj → qk al L, A = A0 as , и M 0 =A0 qk as al B.д) В программе P существует команда вида qi aj → qk al L, A = Λ, и M 0 = qk a0 al B(достраивается новая ячейка слева).Замечание.
В силу недетерминированности для фиксированной конфигурации Mможет существовать несколько конфигураций M 0 , таких, что M `T M 0 . Если M =Aqi aj B и в программе нет команд вида qi aj → . . . (в частности, если i = 0), то вообщене существует конфигурации M 0 такой, что M `T M 0 .Определение. Вычислением на недетерминированной машине Тьюринга T называется любая конечная последовательность конфигураций M0 , M1 , .
. . , Mn для некоторого n ∈ ω, такая, чтоM0 `T M1 `T . . . `T Mn .При этом говорят, что вычисление начинается в конфигурации M0 , заканчиваетсяв конфигурации Mn и имеет длину n (или состоит из n шагов), и пишут M0 `nT Mn .Если M `nT M 0 для некоторого n ∈ ω, то пишут M `∗T M 0 . Если в вычисленииM0 `T . . . `T Mn последнее слово Mn = Aq0 aj B, то говорят, что в данном вычислениипроизошла правильная остановка. Если Mn = Aqi aj B, где i > 0, и в программе неткоманды вида qi aj → . . ., то говорят, что в данном вычислении произошла неправильная остановка.Замечание. Если T — детерминированная машина Тьюринга, то элементы вычисления однозначно определяются по начальной конфигурации M0 .
Поэтому условие¡ ¢(n)M0 `nT Mn равносильно условию Mn = M0 T и можно говорить, что машина Tперерабатывает конфигурацию M0 в конфигурацию Mn .Определение. Пусть T = hA, Q, P, q1 , q0 i — детерминированная машина Тьюринга.Говорят, что язык L над алфавитом A0 ⊆ A \ {0} распознается машиной T , еслидля любого слова w ∈ A∗0 выполняются следующие условия:§ 24. Недетерминированные машины Тьюринга91а) машина T в процессе переработки входной конфигурации q1 0w0 не достраиваетновых ячеек слева;б) если w ∈ L, то машина T перерабатывает конфигурацию q1 0w0 в конфигурациюuq0 1v для некоторых слов u, v ∈ A∗ ;в) если w ∈/ L, то машина T перерабатывает конфигурацию q1 0w0 в конфигурациюuq0 0v для некоторых слов u, v ∈ A∗ .Таким образом, детерминированная машина Тьюринга, распознающая язык L,всегда правильно останавливается на входных словах w ∈ A∗0 и после остановки выдает 1, если w ∈ L, и выдает 0, если w ∈/ L.
Заметим, что в определении нет никакихтребований на поведение машины при запуске с входными словами, содержащимисимволы, не принадлежащие A0 .С помощью недетерминированных машин Тьюринга также можно распознаватьязыки. Однако соответствующее определение выглядит необычным и несимметричным.Определение. Пусть T = hA, Q, P, q1 , q0 i — недетерминированная машина Тьюринга. Говорят, что язык L над алфавитом A0 ⊆ A \ {0} распознается машиной T , еслидля любого слова w ∈ A∗0 выполняются следующие условия:а) в любом вычислении машины T с входной конфигурацией q1 0w0 не достраиваются новые ячейки слева;б) существует натуральное число N , зависящее от T и w, такое, что не существуетконфигурации M с условием q1 0w0 `NT M;в) w ∈ L тогда и только тогда, когда q1 0w0 `∗T uq0 1v для некоторых u, v ∈ A∗ .Таким образом, если недетерминированная машина T распознает язык L, то всеее вычисления, начатые на входном слове w ∈ A∗0 , заканчиваются (это может произойти по двум причинам: либо в вычислении происходит правильная остановка,либо происходит неправильная остановка).
При этом если хотя бы одно вычислениезаканчивается в состоянии q0 и выдает 1, то считается, что слово w распозналось.Даже если в данной ситуации среди остальных ветвей вычислений найдутся такие,которые выдают 0 в состоянии q0 или заканчиваются ввиду неправильной остановки,машина по определению распознает слово w.Пример.
Рассмотрим язык L={an | n — составное число} над алфавитом A0 ={a}.Обычная детерминированная машина Тьюринга, распознающая данный язык,nдействует следующим образом: если на вход подано√ слово a , n > 0, то машинапоследовательно перебирает числа k = 2, 3, . . . , [ n], и для каждого k проверяет,делится ли n на число k. Если хотя бы одно k делит n, то число n — составное, иначе— простое (или меньше двойки).Мы построим недетерминированную машину Тьюринга, которая распознает тотже язык L, но устроена проще.Благодаря недетерминированности циклический пе√ребор чисел k = 2, 3, . . .
, [ n] можно разбить на несколько ветвей параллельных вычислений — для каждого значения k своя ветвь. Если хотя бы одна ветвь окажетсяуспешной, то число — составное. Если все ветви неуспешные, то число — несоставное.Внешний алфавит машины, кроме символов a, 0, 1, будет содержать вспомогательный символ b. Технически работа машины выглядит так. Допустим, на вход машины92Глава V. Теория сложности алгоритмовподано слово 0aaaaaaaaaaaa0 (т. е. n = 12 в данном частном случае). Машина пытается недетерминированно «угадать» нетривиальный делитель k числа n, для этогоона, используя символ b, отмечает в входном слове начальный префикс длины k следующим образом: 0bb0aaaaaaaaa0 (т.
е. k = 3 в данном частном случае). После этогомашина пытается «исчерпать» выбранным префиксом bb0 все буквы a, передвигаяего слева направо примерно так:0bb0aaaaaaaaa0 `∗ 0000bb0aaaaaa0 `∗ 0000000bb0aaa0 `∗ . . .Если входное слово удается покрыть кратным количеством слов вида bb0, то «догадка» машины оказалась правильной. Иначе, т. е. если n не делится нацело на k,данную ветвь вычислений можно считать неуспешной.Программа имеет 13 состояний:q1 0 → q2 0Rq2 a → q3 bRq3 a → q3 bRq3 a → q4 0Lq4 b → q4 bLq4 0 → q5 0Rq5 b → q6 0Rq6 b → q6 bRq6 0 → q7 0Rq7 b → q7 bRq7 a → q8 bLq8 b → q8 bLq8 0 → q9 0Lq 9 b → q4 bq9 0 → q10 0Rq10 0 → q11 0Rq11 b → q11 bRq11 a → q12 0Rq12 0 → q0 1q12 a → q13 aLq13 0 → q4 0LВычисления по данной программе происходят следующим образом.
Начальнаяконфигурация имеет вид q1 0an 0. Если n 6 1, то сразу происходит неправильнаяостановка. Если n > 2, то в состоянии q3 машина недетерминированным образомвыбирает число k, формально производя такие преобразования:q1 0an 0 `∗ 0bk−2 q4 b0an−k 0 = 00sk+t bk−2−t q4 b0bt an−(s+1)k−t 0,при значениях s = 0 и t = 0.Далее запускается двойная циклическая структура.
Внешний цикл имеет счетчикs, а его описанию соответствуют состояния q4 – q13 . Вложенный в него внутреннийцикл имеет счетчик t, ему соответствуют состояния q4 – q9 . Одна циклическая итерация состоит из следующей цепочки преобразований:00sk+t bk−2−t q4 b0bt an−(s+1)k−t 0 `∗ 00sk+t q5 bk−1−t 0bt an−(s+1)k−t 0 `` 00sk+t 0q6 bk−2−t 0bt an−(s+1)k−t 0 `∗ 00sk+t 0bk−2−t 0q7 bt an−(s+1)k−t 0.Если в состоянии q7 обозревается 0, то происходит неправильная остановка, это означает, что либо k не делит n, либо k = n. Иначе цепочка продолжается следующимобразом:00sk+t+1 bk−2−t 0bt q7 an−(s+1)k−t 0 `∗ 00sk+t+1 bk−2−t q8 0bt+1 an−(s+1)k−(t+1) 0.Далее из состояния q8 машина переходит в состояние q9 и смещается на ячейку влево.Если в состоянии q9 обозревается b, то машина переходит на следующую итерацию§ 25.
Классы P и NP93во внутреннем цикле. Если же в состоянии q9 обозревается 0, то, значит, t = k − 2 ицепочка продолжается так:00(s+1)k−2 q9 00bk−1 an−(s+2)k+1 0 `∗ 00(s+1)k bk−1 q11 an−(s+2)k+1 0.Если в состоянии q11 обозревается 0, то происходит неправильная остановка, этоозначает, что n = (s + 2)k − 1, т. е. не делится на k. Иначе цепочка продолжаетсятак:00(s+1)k bk−1 q11 an−(s+2)k+1 0 ` 00(s+1)k bk−1 0q12 an−(s+2)k 0.Если в состоянии q12 обозревается 0, то, значит, k делит n, машина производит правильную остановку и выдает 1. Иначе машина после исполнения последних двухкоманд из программы переходит на следующую итерацию во внешнем цикле.§ 25.Классы P и NPПоскольку детерминированные машины Тьюринга являются частным случаем недетерминированных, то следующее определение мы сформулируем для случая недетерминированных машин.Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
