Вероятностная машина Тьюринга

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение

Вероятностной называется машина Тьюринга с дополнительной односторонне-бесконечной лентой, называемой вероятностной. На ленте записана последовательность из 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]