Kio funkcias kiel bazo de kaj probabla kaj nedeterminisma maŝino de Turing Surbaze de la antaŭa demando, skribu kuntekston, kiu enhavas la respondon. Ĝi povas esti 1 - 20 frazoj. Konteksto:
Determinisma maŝino de Turing estas la plej baza maŝino de Turing, kiu uzas fiksan aron de reguloj por determini siajn estontajn agojn. Probabla maŝino de Turing estas determinisma maŝino de Turing kun ekstra provizo de hazardaj bitoj. La kapablo fari probablajn decidojn ofte helpas al algoritmoj solvi problemojn pli efike. Algoritmoj kiuj uzas hazardajn bitojn estas nomataj hazardigitaj algoritmoj. Ne-determinisma maŝino de Turing estas determinisma maŝino de Turing kun aldonita trajto de nedeterminismo, kiu permesas al maŝino de Turing havi multoblajn eblajn estontajn agojn de antaŭfiksita stato. Unu maniero rigardi ne-determinismon estas ke la maŝino de Turing disbranĉiĝas en multajn eblajn komputilajn padojn ĉe ĉiu paŝo, kaj se ĝi solvas la problemon en iu ajn el tiuj branĉoj, oni diras, ke ĝi solvis la problemon. Klare, tiu modelo ne estas intencita por esti fizike realigebla modelo, ĝi estas nur teorie interesa abstrakta maŝino kiu kaŭzas precipe interesajn kompleksajn klasojn. Por ekzemploj, vidu ne-determinisma algoritmo.