322
правки
Изменения
Нет описания правки
Введем [http://ru.wikipedia.org/wiki/Вероятностное_пространство вероятностное пространство] <tex>(\Omega, \Sigma, \operatorname{P})</tex>, где пространство элементарных исходов <tex>\Omega</tex> — множество всех вероятностных лент, <tex>\Sigma</tex> — сигма-алгебра подмножеств <tex>\Omega</tex>, <tex>\operatorname{P}</tex> — вероятностная мера, заданная на <tex>\Sigma</tex>. Будем считать, что <tex>\Sigma</tex> порождена событиями, зависящими лишь от конечного числа бит вероятностной ленты (то есть существующими в дискретных вероятностных пространствах). Покажем, что любой предикат от ВМТ является событием.
{{Теорема
|statement= Пусть <tex>m</tex> — ВМТ. Тогда для любых <tex>x</tex> и <tex>A</tex> — предиката от <tex>m</tex> выполняется <tex>R = \{r \bigm| A(m(x, r))\} \in \Sigma</tex>, т.е. <tex>R</tex> измеримо.
|proof=
<tex>R = \bigcup\limits_{i = 0}^\infty R_i</tex>, где <tex>R_i = \{r \bigm| A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с <tex>r\}</tex>. Это верно, поскольку мы рассматриваем только завершающиеся ВМТ. Кроме того, из определения <tex>R_i</tex> следует, что они дизъюнктны.
<tex>R_i \in \Sigma</tex> как зависящие от <tex>i</tex> первых битов вероятностной ленты, <tex>\operatorname{P}(R_i) = \frac{1}{2^i} \cdot |\{s : \bigm| |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>.
<tex>R \in \Sigma</tex> как счетное объединение событий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
{{Определение
|definition =
<tex>\mathrm{coRP} = \{L \bigm| \overline L \in \mathrm{RP}\}</tex>.
}}
Класс <tex>\mathrm{coRP}</tex> допускает ошибки программ на словах, не принадлежащих <tex>L</tex>.
