O mașină de probabilitate este un model matematic al unui dispozitiv de calcul în care este implicat un proces aleatoriu. Diverse variante ale conceptului de „Mașină de probabilitate” sunt generalizări ale conceptelor de „automat determinist”, „mașină Turing”, „automat infinit”. De exemplu, astfel de concepte de „mașină de probabilitate” au fost considerate ca: 1) Mașină Turing (sau alt automat determinist) cu o intrare la care este atașat un encoder Bernoulli, care scoate simbolul 1 și 0 cu probabilitatea p și 1 – p, respectiv (0 ⩽ p ⩽ unu). 2) Mașina de probabilitate, care este obținută din mașinile Turing , dacă pentru un simbol vizualizat dat și o stare internă, nu este specificată o singură combinație de simbol, stare, deplasare, ci un tabel de probabilități pentru ca mașina să implementeze fiecare astfel de combinație . (Dacă o mașină Turing este un automat finit, atunci mașina probabilității corespunzătoare este un automat probabilistic finit. 3) Un automat infinit cu un set numărabil de stări, pentru fiecare pereche de stări a căror probabilitate este indicată ca automatul, fiind în a 1-a stare, va merge la a 2-a e. Diferite concepte ale Mașinii Probabilității exprimă diferite niveluri și obiective de abstractizare.
Mașina de probabilitate poate fi folosită pentru a calcula funcții. Rezultatul calculului pe Mașina Probabilității pentru un argument dat nu este definit în mod unic: depinde de implementarea procesului aleatoriu utilizat de mașină. Diferitele rezultate posibile corespund în mod natural probabilităților ca acestea să fie obținute în timpul funcționării mașinii. Este posibil să se stabilească „nivelul de probabilitate” în diferite moduri, ceea ce evidențiază o singură funcție, care va fi considerată o funcție care poate fi calculată. mașina asta. Iată două definiții ale calculabilității unei funcții ale cărei argumente și valori sunt numere naturale: a) funcția f(x) este calculabilă pe Mașina Probabilității T dacă pentru fiecare x probabilitatea ca mașina T, fiind pornită pe argumentul x, nu va mai scrie numărul f(x ); b) funcția f(x) este calculabilă pe Mașina Probabilității T dacă probabilitatea ca pentru tot x mașina T să se oprească după scrierea f(x) este mai mare decât a(0 < a < 1). Funcționarea Mașinii Probabilității poate fi descrisă și în termeni de enumerabilitate a mulțimilor. Definițiile enumerabilității unei mulțimi sunt similare cu definițiile computabilității funcțiilor. Definiția 6), de exemplu, corespunde următoarelor: mulțimea D este enumerabilă pe Mașina Probabilității T dacă probabilitatea ca toate elementele mulțimii D și numai ele să apară la ieșirea mașinii T este mai mare decât a(0 < a < 1). Puteți repara nu un set, ci o întreagă clasă de seturi și să fiți interesat de probabilitatea ca Mașina Probabilității să enumere Ph.D. un set din această clasă (pentru diferite implementări ale unui proces aleatoriu, pot apărea diferite seturi la ieșirea mașinii).
În teoria Mașinii Probabilității sunt studiate următoarele întrebări principale: 1) extinderea clasei de funcții calculabile în trecerea de la mașini deterministe la cele probabilistice (cum depinde această clasă de parametrii probabilistici implicați în definirea Mașinii Probabilității). ); 2) cât de mult același rezultat poate fi obținut mai simplu și mai economic folosind Mașina Probabilității în locul mașinilor deterministe; 3) stabilirea relației dintre diferitele definiții ale Mașinii Probabilității și calculabilitatea pe Mașina Probabilității. În aceste direcții s-au obținut o serie de rezultate. Să enumerăm câteva dintre ele (fapte legate de automatele probabilistice finite). 1. Definițiile calculabilității a) și b) sunt echivalente în sensul că, dacă există o Mașină a Probabilității de tipul I care calculează o funcție în sensul lui a), atunci există și o Mașină a Probabilității de același tip care calculează aceeași funcție și invers. Același lucru este valabil și pentru definițiile corespunzătoare ale enumerabilității. 2. Dacă nu sunt impuse restricții asupra parametrilor probabilistici implicați în definirea Mașinii Probabilității, atunci orice funcție poate fi calculată pe o Mașină a Probabilității adecvată (enumerați orice set). Dacă acești parametri sunt numere reale calculabile, atunci o funcție care este calculabilă pe mașina de probabilitate este, de asemenea, calculabilă pe o mașină deterministă (un set enumerabil pe mașina probabilității este de asemenea enumerabil pe o mașină deterministă). 3. Există funcții recursive care pot fi calculate pe Mașina Probabilității într-un anumit sens mai ușor, cu mai puțin timp (vezi Complexitatea Computațională) decât pe orice mașină deterministă. 4. Există o mulțime atât de infinită încât o mașină deterministă nu poate enumera nicio submulțime infinită a acesteia, dar o mașină de probabilitate potrivită cu probabilitate arbitrar mare produce o mulțime infinită conținută în ea. În acest caz, parametrii probabilistici ai Mașinii Probabilității sunt numere raționale. Teoria Mașina de probabilitate este la fel de abstractă ca și teoria automatelor în general și are aceeași relevanță pentru studiul calculatoarelor și calculelor reale, de exemplu calculele Monte Carlo. Ca argumente și valori ale funcției pe care o calculează Mașina Probabilității, se pot lua nu numai înregistrările numerelor naturale, ci și cuvintele în general într-un alfabet finit și se pot considera această funcție în sens larg, ca comportamentul acestei mașini. . În acest aspect, Mașinile de probabilitate pot servi drept modele în studierea comportamentului dispozitivelor și organismelor cibernetice, de exemplu, în teoria învățării și adaptării.