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

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

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

Определение

Вероятностной называется машина Тьюринга с дополнительной односторонне-бесконечной лентой, называемой вероятностной. На ленте записана последовательность из 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)= p (\{ y | m(x,y) = 1\})[/math]