Вероятностная машина Тьюринга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Определение)
Строка 11: Строка 11:
  
 
==Определение==
 
==Определение==
Множество <tex>A = \bigcup_{p_i} \Omega_{p_i}</tex>. Заметим, что оно [[Измеримое множество|измеримое]]. Вероятностная мера <tex>p(A) = \sum \frac{1}{2^{|p_i|}}</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>.
  
 
==Свойство==
 
==Свойство==

Версия 16:01, 15 апреля 2010

Определение

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

Определение

[math]\Omega[/math] — множество всех вероятностных лент.

Определение

[math]\Omega_p[/math] — множество всех вероятностных лент с префиксом [math]p[/math].

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

Определение

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

Свойство

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

[math]p(m(x)=1)= \mu \{ y | m(x,y) = 1\}[/math]