Просмотр исходного текста страницы Вероятностная машина Тьюринга

==Определение==
Вероятностной называется машина Тьюринга с дополнительной односторонне-бесконечной лентой, называемой вероятностной. На ленте записана последовательность из 0 и 1 с некоторым распределением. Обычно рассматривается равномерное распределение, при котором 0 и 1 равновероятны.

Рассмотрим <tex>\Omega</tex> &mdash; множество всех вероятностных лент и <tex>\Omega_p</tex> &mdash; множество всех вероятностных лент с префиксом <tex>p</tex>.

Вероятностная мера <tex>p(\Omega_p)=\frac{1}{2^{|p|}}</tex>.

==Определение==
Множество <tex>A = \bigcup_{p_i} \Omega_{p_i}</tex>, где <tex>\Omega_{p_i}</tex> дизъюнктны. Заметим, что оно [[Измеримое множество|измеримое]]. Вероятностная мера <tex>p(A) = \sum \frac{1}{2^{|p_i|}}</tex>.

==Свойство==

Вероятность того, что вероятностная машина Тьюринга <tex>m</tex> допускает слово <tex>x</tex> равна мере множества вероятностных лент <tex>y</tex>, при которых <tex>m</tex> допустит <tex>x</tex>. 

<center><tex>P(m(x)=1)= p \{ y | m(x,y) = 1\}</tex></center>