Puc, 12,4, Вычисление no программе M при входе 10100
Функция перехода 5 определена таблицей, где величина, записанная в Г строке и S столбце, есть значение 5 (q, S). Рис. 12.4 иллюстрирует по программе Мпри входе х= 10100, здесь указаны состояние, распространение головки и содержание пустых ячеек ленты до и после каждого шага.
Заметим, что вычисление после восьми шагов оканчивается в состоянии Яу, поэтому на входе 10100 ответом будет «да». В общем случае будем говорить, что программа М, имеющая входной алфавит Г, принимает X е 27* в том и только в том случае, когда, будучи примененной ко входу X, она останавливается в состоянии qy . Язык Lm, распознаваемый программой М, задается следующим образом: Lm= {X е F: М принимает JO-
Нетрудно видеть, что программа, представленная на рис. 12.3, распознает язык: {X е {0,1}; два последних символа словаXявляются нулями}.
Отметим, что это определение распознавания языка не требует, чтобы программа М останавливалась при всех входах из 2?". М обязана останавливаться лишь при входах L.
Если X е I* \ Lm, то работа программы М на X может либо заканчиваться в состоянии Qn, либо может бесконечно продолжаться без остановки. Однако ДМТ-программа, соответствующая нашему пониманию
алгоритма, должна останавливаться на всех словах входного алгоритма. В этом смысле программа на рис. 12.3. является алгоритмической, так как, начиная работать на любом слове из символов 0,1, она будет останавливаться.
Соответствие между «распознаванием» языков и «решением» задач распознавания определяется следующим образом. Будем говорить, что ДМТ-программа М решает задачу распознавания II при кодировании е, если М останавливается на всех словах, составленных из букв входного алфавита 1 = L [II, е]. Программа на рис. 12.3 иллюстрирует это соответствие.
Пример. Делимость на четыре. Дано положительное число N. Существует ли положительное число m такое, что Л= 4т.
При стандартном кодировании целое число N представляется словом из 0,1, т.е. двоичной записью этого числа. Так как положительное целое число делится на четыре тогда и только тогда, когда последние две цифры двоичной записи этого числа являются нулями, то программа, изображенная на рис. 12.4, «решает» при нашем стандартном кодировании задачу «делимость на четыре».
Заметим, что ДМТ-программой можно пользоваться и для вычисления функций. Предположим, что программа М, имеющая входной алфавит Е и ленточный алфавит Г, останавливается на любом входе из I*. Тогда М вычисляет функцию /м.Г* которая для каждого X е 2
определяется следующим образом. Если программа М, начиная работать при входе X, останавливается, то в качестве /м (Х) берется слово, составленное из символов, записанных после остановки машины в ячейке с номерами 1, 2, 3, включая последнюю пустую ячейку. Программа М, представленная на рис. 12.4, вычисляет функциюУл:{0, 1}* -> {О, 1, Ь}*, которая отображает каждое словоX е {0,1 }* в слово fM, получаемое из X удалением двух крайних справа символов (если \Х\<2, то М вьщает в качестве пустое слово). Хорошо известно, что ДМТ-программы могут решать задачи намного более сложные, чем в рассмотренном примере. Несмотря на то что ДМТ имеет только одну последовательную ленту и на каждом шаге может выполнять весьма ограниченную работу, ДМТ-программа может быть составлена так, что проведет любое вычисление, выполняемое обычным компьютером.
Далее определим понятие «временная сложность». Время, требуемое ДМТ-программой Мдля вычисления при входе X, есть число шагов, выполняемых до момента остановки. Если программа Л/останавливается на
всех входах X G 27*, то временную сложность Т: 2 -> 2 можно определить так:
Tm(N) =max
существует такое слово Х&\х\=п т: что вычисление по программе М на входе X требует времени т J
Детерминированная программа М называется полиномиальной ДМТ-программой, если существует такой полином Р, что для всех п е 2, Гд {п)<Р{п).
Далее определим формально первый важный класс языков - класс Р. Он определяется следующим образом: Р = {L: существует полиномиальная ДМТ-программа М, для которой L = L}.
Будем говорить, что задача распознавания II принадлежит классу Р при кодировании е, если i(II, е) е Р, т.е. существует полиномиальная программа ДМТ-программа, которая «решает» задачу при кодировании е. Далее мы не будем приводить конкретные схемы кодирования, а будем говорить, что задача распознавания II принадлежит классу Р.
12.6. Недетерминированное вычисление и класс NP
В настоящем разделе вводится второй важный класс языков (задач распознавания свойств) - класс NP. Прежде чем перейти к формальному определению этого класса в терминах язьпсов и машин Тьюринга, поясним смысл понятия, лежащего в основе определения класса NP.
Рассмотрим задачу коммивояжера. В условии даны множества городов, расстояние между ними и граница В. При этом спрашивается, существует ли маршрут, проходящий через все города, и длины, не превосходящий В, Полиномиальный алгоритм этой задачи неизвестен. Предположим, однако, что относительно некоторой индивидуальной задачи кто-то получил ответ «да». Если вы в этом сомневаетесь, то можно потребовать доказательство этого факта, заключающегося в предъявлении маршрута, обладающего необходимыми свойствами. Имея предъявленное решение, нетрудно проверить является ли оно на самом деле маршрутом и если это так, вычислить его длину, сравнить ее с границей В и тем самым проверить соответствующее утверждение. Более того, эту «процедуру проверки» можно представить в виде алгоритма, временная сложность которого ограничена полиномом от Length (/). Именно понятие полиномиальной проверяемости позволяет вьщелить задачи класса NP. Отметим, что проверяемость за полиномиальное время не влечет