322
правки
Изменения
поправки к теореме о событиях
Используя тезис Черча-Тьюринга, ВМТ можно сопоставить программы, имеющие доступ к случайным битам. Обращение к очередному биту можно трактовать как вызов специальной функции ''random''(). При этом также будем предполагать, что вероятностная лента является неявным аргументом программы или ВМТ, т.е. <tex>p(x) = p(x, r)</tex>, где <tex>r</tex> — вероятностная лента.
Введем [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>\forall x, \forall </tex> и <tex>A</tex> — предиката от <tex>m</tex>: выполняется <tex>R = \{r | 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 | A(m(x, r)), m</tex> прочитала ровно <tex>i</tex> первых символов с вероятностной ленты<tex>\}</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 : |s| = i, s</tex> — префикс <tex>r \in R_i\}|</tex>, <tex>R_i</tex> дизъюнктны.
<tex>R \in \Sigma</tex> как счетное объединение множествсобытий, при этом из их дизъюнктности следует, что <tex>\operatorname{P}(R) = \sum\limits_{i = 0}^{\infty} \operatorname{P}(R_i)</tex>.
}}
