Mikä toimii sekä todennäköisyystön että ei-deterministisen Turingin koneen perustana? Se voi olla 1 - 20 lausetta. - Mitä tarkoitat?
Deterministinen Turingin kone on perus Turingin kone, joka käyttää kiinteitä sääntöjä määrittääkseen tulevia toimintojaan. Todennäköisyysperäinen Turingin kone on deterministinen Turingin kone, jossa on ylimääräinen määrä satunnaisia bittejä. Mahdollisuusarviointi auttaa usein algoritmeja ratkaisemaan ongelmia tehokkaammin. Algoritmeja, jotka käyttävät satunnaisia bittejä, kutsutaan satunnaistetuiksi algoritmeiksi. Ei-deterministinen Turingin kone on deterministinen Turingin kone, jossa on lisätty ei-determinismin ominaisuus, jonka avulla Turingin koneella on useita mahdollisia tulevia toimintoja tietystä tilasta. Yksi tapa nähdä ei-determismi on se, että Turingin kone haarautuu moniksi mahdollisiksi laskentapolkuiksi jokaisessa vaiheessa, ja jos se ratkaisee ongelman missä tahansa näistä haaroista, sen sanotaan ratkaisseen ongelman. On selvää, että tämän mallin ei ole tarkoitus olla fyysisesti toteutettavissa oleva malli, se on vain teoreettisesti mielenkiintoinen abstrakti kone, joka antaa alkunsa erityisen mielenkiintoisille monimutkaisuusluokille. Esimerkkejä näet ei-deterministinen algoritmi.