Todennäköisyyskone on laskentalaitteen matemaattinen malli , jossa on mukana jokin satunnainen prosessi. "Todennäköisyyskoneen" käsitteen erilaiset muunnelmat ovat "deterministisen automaatin", "Turingin koneen", "ääretön automaatin" käsitteiden yleistyksiä. Tällaisia "todennäköisyyskoneen" käsitteitä pidettiin esimerkiksi seuraavasti: 1) Turingin kone (tai muu deterministinen automaatti), jonka sisääntuloon on liitetty Bernoulli-enkooderi, joka tulostaa symbolit 1 ja 0 todennäköisyydellä p ja 1 – p, vastaavasti (0 ⩽ p ⩽ yksi). 2) Todennäköisyyskone, joka saadaan Turingin koneista , jos tietylle katsotulle symbolille ja sisäiselle tilalle ei ole määritetty yksittäistä symbolin, tilan, siirtymän yhdistelmää, vaan todennäköisyystaulukko koneelle toteuttaa jokainen tällainen yhdistelmä. . (Jos Turingin kone on äärellinen automaatti, niin vastaava todennäköisyyskone on äärellinen todennäköisyysautomaatti. 3) Ääretön automaatti, jolla on laskettava tilajoukko, jonka jokaiselle tilaparille ilmoitetaan todennäköisyys, että automaatti, joka on 1. osavaltio, menee 2. e. Todennäköisyyskoneen eri käsitteet ilmaisevat erilaisia abstraktion tasoja ja tavoitteita.
Todennäköisyyskonetta voidaan käyttää funktioiden laskemiseen. Todennäköisyyskoneella suoritettavan laskennan tulos tietylle argumentille ei ole yksiselitteisesti määritelty: se riippuu koneen käyttämän satunnaisprosessin toteutuksesta. Erilaiset mahdolliset lopputulokset vastaavat luonnollisesti todennäköisyyksiä, että ne saadaan koneen käytön aikana. On mahdollista asettaa "todennäköisyystaso" eri tavoilla, mikä erottaa yksittäisen funktion, jota pidetään funktiona, joka on laskettavissa. Tämä auto. Tässä on kaksi määritelmää sellaisen funktion lasketavuudesta, jonka argumentit ja arvot ovat luonnollisia lukuja: a) funktio f(x) on laskettavissa todennäköisyyskoneella T, jos jokaisella x:llä on todennäköisyys, että kone T käynnistetään argumentti x, lopettaa luvun f(x ) kirjoittamisen enemmän; b) funktio f(x) on laskettavissa todennäköisyyskoneella T, jos todennäköisyys, että kaikilla x:illä kone T pysähtyy f(x):n kirjoittamisen jälkeen, on suurempi kuin a(0 < a < 1). Todennäköisyyskoneen toimintaa voidaan kuvata myös joukkojen luettavuudella. Joukon luettavuuden määritelmät ovat samanlaisia kuin funktioiden laskettavuuden määritelmät. Määritelmä 6) vastaa esimerkiksi seuraavaa: joukko D on numeroitavissa todennäköisyyskoneella T, jos todennäköisyys, että joukon D kaikki alkiot ja vain ne esiintyvät koneen T lähdössä, on suurempi kuin a(0 < a < 1). Voit korjata ei yhtä sarjaa, vaan kokonaisen luokan joukkoja ja olla kiinnostunut todennäköisyydestä, että todennäköisyyskone luettelee Ph.D. tämän luokan joukko (satunnaisprosessin eri toteutuksissa koneen lähdössä voi esiintyä erilaisia joukkoja).
Todennäköisyyskoneen teoriassa tutkitaan seuraavia pääkysymyksiä: 1) laskettavien funktioiden luokan laajentaminen siirtyessä deterministisista todennäköisyyskoneisiin (miten tämä luokka riippuu todennäköisyyskoneen määrittelyyn liittyvistä todennäköisyysparametreista ); 2) kuinka paljon sama tulos voidaan saada yksinkertaisemmin ja taloudellisemmin käyttämällä todennäköisyyskonetta determinististen koneiden sijaan; 3) Todennäköisyyskoneen eri määritelmien ja laskettavuuden välisen suhteen määrittäminen todennäköisyyskoneella. Näihin suuntiin on saatu lukuisia tuloksia. Listataanpa joitain niistä (äärellisiin todennäköisyysautomaatteihin liittyviä faktoja). 1. Laskettavuuden a) ja b) määritelmät ovat samat siinä mielessä, että jos on olemassa 1. tyyppinen todennäköisyyskone, joka laskee funktion kohdan a) merkityksessä, on olemassa myös samantyyppinen todennäköisyyskone, joka laskee saman funktion ja päinvastoin. Sama pätee vastaaviin luettavuuden määritelmiin. 2. Jos todennäköisyyskoneen määrittelyyn osallistuville todennäköisyysparametreille ei ole asetettu rajoituksia, mikä tahansa funktio voidaan laskea sopivalla todennäköisyyskoneella (luettelosta mikä tahansa joukko). Jos nämä parametrit ovat laskettavissa olevia reaalilukuja, funktio, joka on laskettavissa todennäköisyyskoneella, on myös laskettavissa deterministisellä koneella (todennäköisyyskoneella numeroitava joukko on myös deterministisellä koneella). 3. On olemassa rekursiivisia funktioita, jotka voidaan laskea todennäköisyyskoneella tietyssä mielessä helpommin, pienemmällä ajalla (katso Laskennallinen monimutkaisuus) kuin millään deterministisellä koneella. 4. On olemassa niin ääretön joukko, että deterministinen kone ei voi luetella mitään sen ääretöntä osajoukkoa, mutta sopiva todennäköisyyskone mielivaltaisen suurella todennäköisyydellä tuottaa siihen sisältyvän äärettömän joukon. Tässä tapauksessa todennäköisyyskoneen todennäköisyysparametrit ovat rationaalilukuja. Teoria Todennäköisyyskone on yhtä abstrakti kuin automaattiteoria yleensä, ja sillä on sama merkitys todellisten tietokoneiden ja laskelmien, esim. Monte Carlon laskelmien, tutkimisessa. Todennäköisyyskoneen laskeman funktion argumentteina ja arvoina voidaan ottaa luonnollisten lukujen tietueiden lisäksi myös sanoja yleensä äärellisissä aakkosissa ja pitää tätä funktiota laajassa merkityksessä tämän koneen käyttäytymisenä. . Tässä suhteessa Todennäköisyyskoneet voivat toimia malleina kyberneettisten laitteiden ja organismien käyttäytymisen tutkimuksessa esimerkiksi oppimisen ja sopeutumisen teoriassa.