322
правки
Изменения
Нет описания правки
|statement= Пусть <tex>m</tex> — ВМТ. Тогда <tex>\forall x, \forall 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 \in \Sigma</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> дизъюнктны.
