Изменения

'''Вероятностная лента''' — бесконечная последовательность битов. Распределение битов на ленте , распределение которых подчиняется некоторому вероятностному закону (обычно считают, что вероятность нахождения <tex>0</tex> или <tex>1</tex> в каждой позиции равна <tex>1/2</tex>).

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

При интерпретации вероятностной машины Используя тезис Черча-Тьюринга как , ВМТ можно сопоставить программы, обращение имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом для программыили ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.<br>В дальнейшем все вероятностные соображения будут относиться к пространству вероятностных лент <tex>r</tex>, вход же программы <tex>x</tex> будем считать фиксированным.

Здесь будет теорема о томВведем вероятностное пространство <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Покажем, что утверждениялюбой предикат от ВМТ является событием.{{Теорема|statement= <tex>\forall A</tex> — предикат от ВМТ: <tex>R = \{r | A(m(x, связанные с ВМТr))\} \in \Sigma</tex>.|proof=Считаем, являются событиямичто <tex>x</tex> фиксирован.