Изменения
Новая страница: «==Определение== Вероятностной лентой называется односторонне-бесконечная лента, в каждой …»
==Определение==
Вероятностной лентой называется односторонне-бесконечная лента, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.
==Определение==
Вероятностной является машина Тьюринга с дополнительной вероятностной лентой.
==Определение==
<tex>\Omega</tex> — множество всех вероятностных лент.
==Определение==
<tex>\Omega_p</tex> — множество префиксов всех вероятностных лент, каждый из которых длины <tex>p</tex>.
==Свойства==
<tex>1)</tex> <tex>p(\Omega_p)=\frac{1}{2^{|p|}}</tex>
<tex>2)</tex> Множество <tex>A = \bigcup_{p_i} \Omega_{p_i}</tex>. Заметим, что оно [[Измеримое множество|измеримое]]. <tex>p(A) = \sum \frac{1}{2^{|p_i|}}</tex>
<tex>3)</tex> Вероятность того, что вероятностная машина Тьюринга <tex>m</tex> допускает слово <tex>x</tex> равна мере множества вероятностных лент, при которых <tex>m</tex> допустит <tex>x</tex>.
<center><tex>p(m(x)=1)= \mu \{ y | m(x,y) = 1\}</tex></center>
Вероятностной лентой называется односторонне-бесконечная лента, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.
==Определение==
Вероятностной является машина Тьюринга с дополнительной вероятностной лентой.
==Определение==
<tex>\Omega</tex> — множество всех вероятностных лент.
==Определение==
<tex>\Omega_p</tex> — множество префиксов всех вероятностных лент, каждый из которых длины <tex>p</tex>.
==Свойства==
<tex>1)</tex> <tex>p(\Omega_p)=\frac{1}{2^{|p|}}</tex>
<tex>2)</tex> Множество <tex>A = \bigcup_{p_i} \Omega_{p_i}</tex>. Заметим, что оно [[Измеримое множество|измеримое]]. <tex>p(A) = \sum \frac{1}{2^{|p_i|}}</tex>
<tex>3)</tex> Вероятность того, что вероятностная машина Тьюринга <tex>m</tex> допускает слово <tex>x</tex> равна мере множества вероятностных лент, при которых <tex>m</tex> допустит <tex>x</tex>.
<center><tex>p(m(x)=1)= \mu \{ y | m(x,y) = 1\}</tex></center>
