En sannolikhetsmaskin är en matematisk modell av en datorenhet där någon slumpmässig process är inblandad. Olika varianter av begreppet "Probability Machine" är generaliseringar av begreppen "deterministisk automat", "Turingmaskin", "oändlig automat". Till exempel ansågs sådana begrepp för en "sannolikhetsmaskin" som: 1) Turingmaskin (eller annan deterministisk automat) med en ingång till vilken en Bernoulli-kodare är ansluten, som matar ut symbolen 1 och 0 med sannolikheten p och 1 – p, respektive (0 ⩽ p ⩽ en). 2) Sannolikhetsmaskin, som erhålls från Turing-maskiner, om för en given visad symbol och internt tillstånd, inte en enda kombination av symbol, tillstånd, skift specificeras, utan en tabell över sannolikheter för maskinen att implementera varje sådan kombination. (Om en Turing-maskin är en finit automat, så är motsvarande sannolikhetsmaskin en finit probabilistisk automat. 3) En oändlig automat med en räknebar uppsättning tillstånd, för varje tillståndspar vars sannolikhet anges att automaten är i det första tillståndet, kommer att gå till det andra e. Olika koncept av sannolikhetsmaskinen uttrycker olika abstraktionsnivåer och mål.
Sannolikhetsmaskinen kan användas för att beräkna funktioner. Resultatet av beräkningen på sannolikhetsmaskinen för ett givet argument är inte unikt definierat: det beror på implementeringen av den slumpmässiga processen som används av maskinen. Olika möjliga utfall motsvarar naturligtvis sannolikheten för att de kommer att erhållas under maskinens drift. Det är möjligt att ställa in "sannolikhetsnivån" på olika sätt, vilket pekar ut en enskild funktion, som kommer att betraktas som en funktion som är beräkningsbar på. den här bilen. Här är två definitioner av beräkningsbarheten för en funktion vars argument och värden är naturliga tal: a) funktionen f(x) är beräkningsbar på sannolikhetsmaskinen T om sannolikheten för varje x är att maskinen T startas på argument x, kommer att sluta skriva talet f(x ) mer; b) funktionen f(x) är beräkningsbar på sannolikhetsmaskinen T om sannolikheten att maskinen T stannar för alla x efter att ha skrivit f(x) är större än a(0 < a < 1). Sannolikhetsmaskinens funktion kan också beskrivas i termer av uppräknbarhet av uppsättningar. Definitionerna av räknebarhet för en uppsättning liknar definitionerna av beräkningsbarhet av funktioner. Definition 6, till exempel, motsvarar följande: mängden D är uppräknbar på sannolikhetsmaskinen T om sannolikheten att alla element i mängden D och endast de förekommer vid maskinens Ts utgång är större än a(0 < a < 1). Du kan fixa inte en uppsättning, utan en hel klass av uppsättningar och vara intresserad av sannolikheten att Probability Machine kommer att räkna upp Ph.D. en uppsättning av denna klass (för olika implementeringar av en slumpmässig process kan olika uppsättningar visas vid maskinens utgång).
I teorin om sannolikhetsmaskinen studeras följande huvudfrågor: 1) utvidgningen av klassen av beräkningsbara funktioner i övergången från deterministiska till probabilistiska maskiner (hur denna klass beror på de probabilistiska parametrar som är involverade i definitionen av sannolikhetsmaskinen ); 2) hur mycket samma resultat kan erhållas enklare och mer ekonomiskt med hjälp av sannolikhetsmaskinen istället för deterministiska maskiner; 3) upprättande av förhållandet mellan olika definitioner av sannolikhetsmaskinen och beräkningsbarhet på sannolikhetsmaskinen. Ett antal resultat har erhållits i dessa riktningar. Låt oss lista några av dem (fakta relaterade till finita probabilistiska automater). 1. Definitionerna av beräkningsbarhet a) och b) är ekvivalenta i den meningen att om det finns en sannolikhetsmaskin av den första typen som beräknar en funktion i betydelsen a), så finns det också en sannolikhetsmaskin av samma typ som beräknar samma funktion och vice versa. Detsamma gäller för motsvarande definitioner av räkning. 2. Om inga begränsningar åläggs de probabilistiska parametrarna som är involverade i definitionen av sannolikhetsmaskinen, kan vilken funktion som helst beräknas på en lämplig sannolikhetsmaskin (lista vilken uppsättning som helst). Om dessa parametrar är beräkningsbara reella tal, så kan en funktion som är beräkningsbar på sannolikhetsmaskinen också beräknas på en deterministisk maskin (en uppsättning som kan räknas upp på sannolikhetsmaskinen kan också räknas upp på en deterministisk maskin). 3. Det finns rekursiva funktioner som är beräkningsbara på sannolikhetsmaskinen i en viss mening lättare, med mindre tid (se Computational Complexity) än på någon deterministisk maskin. 4. Det finns en sådan oändlig mängd att en deterministisk maskin inte kan räkna upp någon oändlig delmängd av den, men en lämplig sannolikhetsmaskin med godtyckligt hög sannolikhet producerar en oändlig mängd som ingår i den. I det här fallet är de probabilistiska parametrarna för Probability Machine rationella tal. Teori Sannolikhetsmaskin är lika abstrakt som automatteori i allmänhet, och har samma relevans för studier av riktiga datorer och beräkningar, t.ex. Monte Carlo-beräkningar. Som argument och värden för funktionen som sannolikhetsmaskinen beräknar, kan man ta inte bara register över naturliga tal, utan också ord i allmänhet i ett ändligt alfabet och betrakta denna funktion i vid mening, som beteendet hos denna maskin . I denna aspekt kan sannolikhetsmaskiner fungera som modeller för att studera beteendet hos cybernetiska enheter och organismer, till exempel i teorin om inlärning och anpassning.