Hvad der tjener som basis for både probabilistiske og ikke-deterministiske Turingmaskiner Givet det foregående spørgsmål, skriv en sammenhæng, der indeholder svaret. Det kan være 1 - 20 sætninger. Kontekst:
En deterministisk Turingmaskine er den mest basale Turingmaskine, der bruger et fast sæt regler til at bestemme sine fremtidige handlinger. En probabilistisk Turingmaskine er en deterministisk Turingmaskine med en ekstra forsyning af tilfældige bits. Evnen til at træffe sandsynlighedsbaserede beslutninger hjælper ofte algoritmer med at løse problemer mere effektivt. Algoritmer, der bruger tilfældige bits kaldes randomiserede algoritmer. En ikke-deterministisk Turingmaskine er en deterministisk Turingmaskine med en ekstra funktion af ikke-determinisme, som gør det muligt for en Turingmaskine at have flere mulige fremtidige handlinger fra en given tilstand. En måde at betragte ikke-determinisme på er, at Turingmaskinen forgrener sig i mange mulige beregningsveje i hvert trin, og hvis den løser problemet i nogen af disse grene, siges det at have løst problemet. Det er klart, at denne model ikke er beregnet til at være en fysisk gennemførlig model, det er bare en teoretisk interessant abstrakt maskine, der giver anledning til særligt interessante kompleksitet klasser. For eksempler, se ikke-deterministisk algoritme.