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

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

Всюду далее двоичный алфавит \(\{ 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)\,\).

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


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.