Una máquina de probabilidad es un modelo matemático de un dispositivo informático en el que interviene algún proceso aleatorio. Varias variantes del concepto de "Máquina de probabilidad" son generalizaciones de los conceptos de "autómata determinista", "máquina de Turing", "autómata infinito". Por ejemplo, tales conceptos de una "máquina de probabilidad" se consideraron como: 1) Máquina de Turing (u otro autómata determinista) con una entrada a la que se adjunta un codificador de Bernoulli, que emite el símbolo 1 y 0 con probabilidad p y 1 - p, respectivamente (0 ⩽ p ⩽ uno). 2) La máquina de probabilidad, que se obtiene de las máquinas de Turing , si para un símbolo visto dado y un estado interno, no se especifica una sola combinación de símbolo, estado, cambio, sino una tabla de probabilidades para que la máquina implemente cada una de esas combinaciones. . (Si una máquina de Turing es un autómata finito, entonces la Máquina de Probabilidad correspondiente es un autómata probabilístico finito. 3) Un autómata infinito con un conjunto contable de estados, para cada par de estados de los cuales se indica la probabilidad de que el autómata, estando en el 1er estado, pasará al 2do e. Diferentes conceptos de la Máquina de Probabilidad expresan diferentes niveles y objetivos de abstracción.
La máquina de probabilidad se puede utilizar para calcular funciones. El resultado del cálculo en la Máquina de Probabilidad para un argumento dado no está definido unívocamente: depende de la implementación del proceso aleatorio utilizado por la máquina. Los diferentes resultados posibles corresponden naturalmente a las probabilidades de que se obtengan en el curso de la operación de la máquina. Es posible establecer el "nivel de probabilidad" de varias maneras, lo que singulariza una sola función, que se considerará una función computable. este carro. He aquí dos definiciones de la computabilidad de una función cuyos argumentos y valores son números naturales: a) la función f(x) es computable en la Máquina de Probabilidades T si para cada x la probabilidad de que la máquina T, siendo iniciada en la argumento x, dejará de escribir el número f(x ) más; b) la función f(x) es computable en la Máquina de Probabilidades T si la probabilidad de que para todo x la máquina T se detenga después de escribir f(x) es mayor que a(0 < a < 1). La operación de la Máquina de Probabilidad también se puede describir en términos de enumerabilidad de conjuntos. Las definiciones de enumerabilidad de un conjunto son similares a las definiciones de computabilidad de funciones. La definición 6), por ejemplo, corresponde a lo siguiente: el conjunto D es enumerable en la Máquina de Probabilidades T si la probabilidad de que todos los elementos del conjunto D y sólo ellos aparezcan a la salida de la máquina T es mayor que a(0 < un < 1). Puede corregir no un conjunto, sino toda una clase de conjuntos y estar interesado en la probabilidad de que la Máquina de probabilidad enumere Ph.D. un conjunto de esta clase (para diferentes implementaciones de un proceso aleatorio, pueden aparecer diferentes conjuntos en la salida de la máquina).
En la teoría de la Máquina de Probabilidades se estudian las siguientes cuestiones principales: 1) la extensión de la clase de funciones computables en la transición de máquinas deterministas a máquinas probabilísticas (cómo esta clase depende de los parámetros probabilísticos involucrados en la definición de la Máquina de Probabilidades ); 2) cuánto se puede obtener el mismo resultado de manera más simple y económica utilizando la Máquina de Probabilidad en lugar de máquinas deterministas; 3) establecimiento de la relación entre varias definiciones de la Máquina de Probabilidad y la computabilidad en la Máquina de Probabilidad. Se han obtenido varios resultados en estas direcciones. Enumeremos algunos de ellos (hechos relacionados con autómatas probabilísticos finitos). 1. Las definiciones de computabilidad a) y b) son equivalentes en el sentido de que si existe una Máquina de Probabilidad del 1er tipo que calcula una función en el sentido de a), entonces también existe una Máquina de Probabilidad del mismo tipo que calcula la misma función, y viceversa. Lo mismo es cierto para las definiciones correspondientes de enumerabilidad. 2. Si no se imponen restricciones a los parámetros probabilísticos involucrados en la definición de la Máquina de Probabilidad, entonces se puede calcular cualquier función en una Máquina de Probabilidad adecuada (enumere cualquier conjunto). Si estos parámetros son números reales computables, entonces una función que es computable en la Máquina de probabilidad también es computable en una máquina determinista (un conjunto enumerable en la Máquina de probabilidad también es enumerable en una máquina determinista). 3. Hay funciones recursivas que son computables en la Máquina de Probabilidad en cierto sentido más fácil, con menos tiempo (ver Complejidad Computacional) que en cualquier máquina determinista. 4. Existe un conjunto tan infinito que una máquina determinista no puede enumerar ningún subconjunto infinito del mismo, pero una Máquina de Probabilidad adecuada con una probabilidad arbitrariamente alta produce un conjunto infinito contenido en él. En este caso, los parámetros probabilísticos de la Máquina de Probabilidad son números racionales. Teoría La máquina de probabilidad es tan abstracta como la teoría de los autómatas en general, y tiene la misma relevancia para el estudio de las computadoras y los cálculos reales, por ejemplo, los cálculos de Monte Carlo. Como argumentos y valores de la función que calcula la Máquina de Probabilidades, se pueden tomar no sólo los registros de los números naturales, sino también las palabras en general en un alfabeto finito y considerar esta función en un sentido amplio, como el comportamiento de esta máquina. . En este aspecto, las Máquinas de Probabilidad pueden servir como modelos en el estudio del comportamiento de dispositivos y organismos cibernéticos, por ejemplo, en la teoría del aprendizaje y la adaptación.