ВЕРОЯТНОСТНАЯ МАШИНА

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

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

В теории В. м. изучаются следующие осн. вопросы: 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. Агафонов.