Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4.2 Машины Тьюринга
Для того чтобы дать точное определение эффективной процедуры (т.е. алгоритма), Тьюринг изобрел воображаемое вычислительное устройство, называемое машиной Тьюринга (Turing machine) и представляющее собой элементарную, но достаточно общую модель вычислений. Она позволяет описать вопросы, связанные с вычислительной сложностью. Ниже мы рассмотрим вариант машины Тьюринга, вполне достаточный для раскрытия темы. Общее описание машины Тьюринга дано в разделе 1.6 работы [9].
В нашем варианте машина Тьюринга (рис. 4.1) состоит из управляющего
120
Часть II. Математические основы
Управляющее устройство с конечным числом состояний Печатающая
/ головка
Лента 1
Лента 2
Лента к
Ячейка
Рис. 4.1. Машина Тьюринга
(tapes) и такого же количества головок (tapeheads). Управляющее устройство контролирует операции, выполняемые головками, которые считывают информацию с лент или записывают ее на ленту. Каждая головка имеет доступ к своей ленте и может перемещаться вдоль нее влево и вправо. Каждая лента разделена на бесконечное количество ячеек (cells). Машина решает задачу, перемещая головку вдоль строки, состоящей из конечного количества символов, расположенных последовательно, начиная с крайней левой ячейки. Каждый символ занимает одну ячейку, а оставшиеся ячейки ленты, расположенные справа, остаются пустыми (blank). Описанная выше строка называется исходными данными задачи (input). Сканирование начинается с крайней слева ячейки ленты, содержащей исходные данные, когда машина находится в предписанном начальном состоянии (initial state). В каждый момент времени только одна из головок имеет доступ к своей ленте. Операция доступа головки к своей ленте называется тактом (legal move). Если машина начинает работу с начального состояния, последовательно выполняет такты, сканирует исходную строку и завершает работу, достигая заключительного состояния (termination condition), говорят, что машина распознает
Глава 4. Вычислительная сложность
121
(recognize) исходные данные. В противном случае в некоторый момент машина не может выполнить очередной такт и останавливается, не распознав исходные данные. Исходные данные, распознаваемые машиной Тьюринга, называются предложением (instance) распознаваемого языка (language).
Для каждой конкретной задачи машину Тьюринга можно полностью определить с помощью функции, описывающей работу управляющего устройства с конечным числом состояний. Такая функция может иметь вид таблицы, в которой для каждого состояния указана операция, выполняемая на следующем такте. В свое время мы рассмотрим пример и описание машины Тьюринга (пример 4.1).
Количество тактов Тм, которые машина Тьюринга М должна выполнить при распознавании исходной строки, называется продолжительностью работы или временной сложностью (time complexity) машины М. Очевидно, что величину Тм можно представить в виде функции Тм{п) : N ¦—> N, где п — длина (length), или размер (size), исходного предложения, т.е. количество символов, из которых состоит исходная строка, когда машина М пребывает в начальном состоянии. Легко видеть, что Тм(п) ^ п. Кроме временных ограничений, машина М имеет ограничения памяти Sm, представляющие собой количество ячеек, которые доступны для записи. Величину Sm также можно представить в виде функции $м{п) : N |—> N, которая называется пространственной сложностью (space complexity) машины М.
Конкретная машина Тьюринга будет рассмотрена в следующем разделе.
4.3 Детерминированное полиномиальное время
Начнем с рассмотрения класса языков, распознаваемых детерминированными машинами Тьюринга за полиномиальное время (polynomial time). Функция p(n) является полиномиальной по целому аргументу п, если она имеет вид
p(n) = cknk + cfc_infc-1 Н----+ an + со, (4.3.1)
где числа к и Cj(z = 0,1,2,...,А;) — целые константы, причем с* ф 0. Число к > 0 называется степенью (degree) полинома и обозначается как deg(p(n)), а числа Cj называются коэффициентами (coefficients) полинома р(п).
Определение 4.1 (Класс "Р). Символом V обозначается класс языков, имеющих следующие характеристики. Язык L принадлежит классу V, если существует машина Тьюринга М и полином р{п), такие что машина М распознает любое предложение I ?L за время Тм(п), где Тм{п) ^ р(п) для всех неотрицательных целых чисел п, an — параметр, задающий длину предложения I. В этом случае говорят, что язык L распознается за полиномиальное время.
122
Часть II. Математические основы
Проще говоря, языки, распознаваемые за полиномиальное время, считаются "всегда простыми", а полиномиальные машины Тьюринга — "всегда эффективными" (смысл терминов "простой язык" и "эффективная машина" будет раскрыт в разделе 4.4.6). Рассмотрим смысл слова "всегда". Все машины Тьюринга, распознающие язык L из класса V, называются детерминированными (deterministic). Детерминированная машина Тьюринга порождает результат, который полностью предопределен исходными данными и начальным состоянием машины. Иначе говоря, повторный запуск машины Тьюринга с теми же исходными данными и начальным состоянием приводит к идентичным результатам.
