Вероятностная машина Тьюринга

Материал из Циклопедии
Перейти к: навигация, поиск

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

[править] Описание

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

Существует также альтернативное определение:

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

Всюду далее двоичный алфавит [math]\{ 0,1\}\,[/math] мы будем обозначать через [math]\Sigma\,[/math]. Тогда [math]\Sigma ^*\,[/math] — множество всех конечных двоичных строк и [math]\Sigma ^n=\{ x: x\in \Sigma ^*, |x|=n\}\,[/math] — множество всех двоичных строк длины [math]n\,[/math].

Для всякой функции [math]f:\Sigma ^*\rightarrow \Sigma ^*\,[/math] через [math]f_n\,[/math] обозначается ее ограничение на множество [math]\Sigma ^n\,[/math], то есть конечная функция, определенная на двоичных строках длины [math]n\,[/math]. Таким образом, функцию [math]f\,[/math] можно рассматривать просто как сокращенное обозначение для семейства функций [math]\{ f_n, n\in N\}\,[/math].

Поскольку в теоретической криптографии рассматриваются, в основном, вероятностные вычисления, необходима строго определенная модель таких вычислений. Наиболее удобной моделью является вероятностная машина Тьюринга. Она отличается от обычной, детерминированной, машины Тьюринга тем, что может «подбрасывать монету», то есть использовать в процессе вычислений исходы экспериментов по выбору случайного бита, принимающего каждое из значений 0 и 1 с вероятностью 1/2.

Выходом вероятностной машины Тьюринга на входе [math]x\,[/math] является случайная величина. Интуитивно, вероятностная машина Тьюринга вычисляет функцию [math]f\,[/math], если для всякого входа [math]x\,[/math] из области определения эта случайная величина принимает значение [math]f(x)\,[/math] ``с достаточно большой вероятностью".

Формально, вероятностную машину Тьюринга [math]M\,[/math] мы определяем следующим образом. Помимо обычной ленты, на которую записано входное слово [math]x\,[/math] и которая доступна машине [math]M\,[/math] и на чтение, и на запись, имеется еще дополнительная лента, содержащая случайную строку [math]r\,[/math] и доступная [math]M\,[/math] только на чтение. Пусть [math]\Sigma ^{\infty}\,[/math] обозначает множество всех бесконечных двоичных последовательностей. Можно считать, что на дополнительной ленте машины [math]M\,[/math] (в дальнейшем мы будем называть ее случайной лентой) записана бесконечная случайная последовательность битов [math]r\in _R \Sigma ^{\infty}[/math] и читающая головка машины [math]M\,[/math] в начальный момент времени обозревает первый бит этой последовательности. Процесс вычисления вероятностной машины [math]M\,[/math] определяется таким же образом, как это делается для обычной, детерминированной, машины Тьюринга, с той лишь разницей, что у машины [math]M\,[/math] имеется дополнительная лента и дополнительный вход [math]r\,[/math].

Определение. Говорят, что вероятностная машина Тьюринга [math]M\,[/math] работает за полиномиальное время, если существует такой полином [math]p\,[/math], что для всех [math]n\,[/math], для любых [math]x\in \Sigma ^n\,[/math] и [math]r\in \Sigma ^{\infty}\,[/math] машина [math]M\,[/math] на входе [math](x,r)\,[/math] останавливается через не более чем [math]p(n)\,[/math] шагов.

Во всяком вычислении, в котором машина [math]M\,[/math] останавливается, она может использовать лишь префикс конечной длины последовательности [math]r\,[/math]. В частности, очевидно, что если машина [math]M\,[/math] работает за полиномиальное время, то на любом входе [math]x\,[/math] длины [math]n\,[/math] она может использовать не более [math]p(n)\,[/math] случайных битов.

В приведенном выше определении машина [math]M\,[/math] должна останавливаться через полиномиальное число шагов всегда, то есть при любой последовательности [math]r\,[/math]. Более слабое определение требует, чтобы это происходило ``почти всегда".

Тезис Эдмонда. Эффективные алгоритмы — это полиномиальные алгоритмы.

Определение. Пусть [math]t_M(x, r)\,[/math] — число шагов вероятностной машины Тьюринга [math]M\,[/math] на входе [math]x\,[/math], когда на случайной ленте записана последовательность [math]r\,[/math]. Говорят, что машина [math]M\,[/math] работает за полиномиальное в среднем время, если существует такая константа [math]\varepsilon \gt0\,[/math], что для всех [math]x\in \Sigma ^n\,[/math]

[math]E((t_M(x, r))^\varepsilon )\leq n.[/math]

Здесь [math]E\,[/math] — математическое ожидание; [math]t_M(x,r)\,[/math] рассматривается как случайная величина при фиксированной строке [math]x\,[/math] и случайной последовательности [math]r\,[/math].

Для каждого фиксированного входа [math]x\in \Sigma ^*\,[/math], выходом вероятностной машины Тьюринга [math]M\,[/math] будет случайная величина, обозначаемая через [math]M(x)\,[/math].

[править] Другие алгоритмы

[править] Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты