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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
Вероятностной является машина Тьюринга с дополнительной односторонне-бесконечной лентой, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.
+
Вероятностной лентой называется односторонне-бесконечная лента, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.
 +
 
 
==Определение==
 
==Определение==
Множество называется измеримым, если представимо в виде отрезков.
+
Вероятностной является машина Тьюринга с дополнительной вероятностной лентой.
  
 
==Определение==
 
==Определение==
Строка 9: Строка 10:
 
==Определение==
 
==Определение==
 
<tex>\Omega_p</tex> &mdash; множество префиксов всех вероятностных лент, каждый из которых длины <tex>p</tex>.
 
<tex>\Omega_p</tex> &mdash; множество префиксов всех вероятностных лент, каждый из которых длины <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>

Текущая версия на 19:20, 4 сентября 2022

Определение

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

Определение

Вероятностной является машина Тьюринга с дополнительной вероятностной лентой.

Определение

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

Определение

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

Свойства

[math]1)[/math] [math]p(\Omega_p)=\frac{1}{2^{|p|}}[/math]

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

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

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