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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Пусть $t_{M}(x,r)\,$ — число шагов вероятностной машины Тьюринга $M\,$ на входе $x\,$, когда на случайной ленте записана последовательность $r\,$. Говорят, что машина $M\,$ работает за полиномиальное в среднем время, если существует такая константа $\varepsilon >0\,$, что для всех $x\in \Sigma ^{n}\,$

$E((t_{M}(x,r))^{\varepsilon })\leq n.$

Здесь $E\,$ — математическое ожидание; $t_{M}(x,r)\,$ рассматривается как случайная величина при фиксированной строке $x\,$ и случайной последовательности $r\,$.

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

Другие алгоритмы

• метод математической индукции;
• алгоритмы в арифметике;
• алгоритмы перевода чисел;
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест;
• логистические алгоритмы;
• алгоритмы решения транспортных задач;
• численные методы;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• синтез автомата Мили;
• синтез автомата Мура.

Ссылки

• Курс Н. П. Варновского Понятия теории сложности вычислений