Машина вероятности

Машина вероятности – математическая модель вычислительного устройства, в работе которого участвует некоторый случайный процесс. Различные варианты понятия «Машины вероятности» являются обобщениями понятий «автомата детерминированного», «Тьюринга машина», «автомата бесконечного». Рассматривались, например, такие понятия «машины вероятности», как: 1)Машина Тьюринга (или другой детерминированный автомат) с входом, к которому присоединен бернуллиевский датчик, выдающий символ 1 и 0 с вероятностью p и 1 – p соответственно (0 ⩽ p ⩽ 1). 2) Машина вероятности, которая получается из машин Тьюринга, если для данного обозреваемого символа и внутреннего состояния задается не единственная комбинация символ, состояние, сдвиг», а таблица вероятностей осуществления машиной каждой такой комбинации. (Если машина Тьюринга является конечным автоматом, то соответствующая Машина вероятности – это конечный вероятностный автомат. 3) Бесконечный автомат со счетным множеством состояний, для каждой пары состояний которого указывается вероятность того, что автомат, находясь в 1-м состоянии, перейдет во 2-е. Различные понятия Машина вероятности выражают различные уровни и цели абстракции.

Вычисление функций

Машину вероятности можно использовать для вычисления функций. Результат вычисления на Машину вероятности для данного аргумента определен не однозначно: он зависит от реализации случайного процесса, используемого машиной. Различным возможным результатом естественным образом соответствуют вероятности того, что они будут получены в процессе работы машины. Можно различными способами задавать «уровень вероятности», выделяющий единственную функцию, которая и будет считаться функцией, вычислимой на. этой машине. Приведем два определения вычислимости функции, аргументами и значениями которой являются натуральные числа: а) функция f(x)вычислима на Машине вероятности Т, если для каждого x вероятность того, что машина Т, будучи запущена на аргументе x остановится, записав число f(x) больше; б) функция f(x) вычислима на Машине вероятности Т, если вероятность того, что для всех x машина Т остановится, записав f(x) больше а(0 < a < 1). Работу Машины вероятности можно также описывать в терминах перечислимости множеств. Определения перечислимости множества аналогичны определениям вычислимости функций. Определению 6), например, соответствует такое: множество D перечислимо на Машине вероятности Т, если вероятность того, что все элементы множества D и только они появятся на выходе машины Т, больше а(0 < a < 1). Можно фиксировать не одно множество, а целый класс множеств и интересоваться вероятностью того, что Машина вероятности перечислит к.-н. множество этого класса (для разных реализаций случайного процесса на выходе машины могут появляться разные множества).

Основные вопросы

В теории Машины вероятности изучаются следующие основные вопросы: 1) расширение класса вычислимых функций при переходе от детерминированных машин к вероятностным (как этот класс зависит от вероятностных параметров, участвующих в определении Машины вероятности); 2) насколько один и тот же результат можно получить проще и экономнее, используя Машину вероятности вместо детерминированных машин; 3) установление взаимосвязи между различными определениями Машины вероятности и вычислимости на Машину вероятности. В этих направлениях получен ряд результатов. Перечислим некоторые из них (факты, относящиеся к конечным вероятностным автоматам). 1. Определения вычислимости а) и б) эквивалентны в том смысле, что если существует Машина вероятности 1-го типа, вычисляющая функцию в смысле а), то существует и Машина вероятности того же типа, вычисляющая ту же функцию , и наоборот. То же верно для соответствующих определений перечислимости. 2. Если на вероятностные параметры, участвующие в определении Машины вероятности не налагать никаких ограничений, то любую функцию можно вычислить на подходящей Машину вероятности (перечислить любое множество). Если эти параметры являются вычислимыми действительными числами, то функция, вычислимая на Машине вероятности, вычислима и на детерминированной машине (множество, перечислимое на Машине вероятности, перечислимо и на детерминированной машине). 3. Существуют рекурсивные функции, которые вычислимы на Машине вероятности в некотором смысле проще, с меньшей затратой времени (см. Сложность вычислений) чем на любой детерминированной машине. 4. Существует такое бесконечное множество, что детерминированная машина не может перечислить никакое бесконечное его подмножество, но подходящая Машина вероятности со сколь угодно большой вероятностью выдает бесконечное множество, содержащееся в нем. При этом вероятностные параметры Машины вероятности являются рациональными числами. Теория Машина вероятности является в такой же степени абстрактной, как и вообще автоматов теория, и имеет такое же отношение к изучению реальных вычислительных машин и вычислений, напр., вычислений методом Монте-Карло. В качестве аргументов и значений функции, которую вычисляет Машина вероятности, можно брать не только записи натуральных чисел, но и вообще слова в конечном алфавите и рассматривать эту функцию в широком смысле, как поведение этой машины. В этом аспекте Машина вероятности могут служить моделями при изучении поведения кибернетических устройств и организмов, напр., в теории обучения и адаптации.

См. также

• Вероятностный автомат

Литература

• Барздинь Я. М. О вычислимости на вероятностных машинах
• «Доклады АН СССР. Серия математика, физика», 1969, т. 189, № 4; Леу К. де
• Вычислимость на вероятностных машинах. В кн.: Автоматы. Пер. с англ. М., 1956; Рабин М. О. Вероятностные автоматы
• Кибернетический сборник, Ne 9. М., 1964; Рaz A. Introduction to probabilistic automata. New York - London, 1971. В. H. Агафонов