Изменения

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

==Определение==Вероятностной является машина Тьюринга с дополнительной вероятностной лентой. ==Определение==Рассмотрим <tex>\Omega</tex> &mdash; множество всех вероятностных лент. ==Определение==и <tex>\Omega_p</tex> &mdash; множество всех вероятностных лент с префиксом <tex>p</tex>.

==ОпределениеВероятности событий, связанных с машиной Тьюринга==Множество Рассмотрим некоторое событие, связанное с машиной Тьюринга. Так как машина заканчивает свою работу за конечное время, она успевает рассмотреть конечное число ячеек на вероятностной ленте. Поэтому любое такое событие можно представить в виде <tex>A = \bigcup_{p_i} \Omega_{p_i}</tex>. Заметим, что оно [[Измеримое множество|измеримое]]. где <tex>p(A) = \sum \frac{1}Omega_{2^{|p_i|}}</tex> ==Свойства== <tex>1)</tex> дизъюнктны. Заметим, что оно измеримое, так как представляет собой объединение отрезков. Вероятностная мера <tex>p(\Omega_pA)=\sum \frac{1}{2^{|pp_i|}}</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>y</tex>, при которых <tex>m</tex> допустит допускает <tex>x</tex>.

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