Mi szolgál mind a valószínűségi, mind a nem-determinisztikus Turing-gépek alapjaként Az előző kérdést figyelembe véve írjunk egy összefüggést, amely tartalmazza a választ. Lehet 1 - 20 mondat. A szövegkörnyezet:
A determinisztikus Turing-gép a legegyszerűbb Turing-gép, amely rögzített szabályokat használ a jövőbeni cselekedeteinek meghatározására. A valószínűségi Turing-gép egy determinisztikus Turing-gép, amely extra mennyiségű véletlenszerű bitet tartalmaz. A valószínűségi döntések meghozatalának képessége gyakran segít az algoritmusoknak a problémák hatékonyabb megoldásában. A véletlenszerű biteket használó algoritmusokat randomizált algoritmusoknak nevezzük. A nem-determinisztikus Turing-gép egy determinisztikus Turing-gép, a nem-determinizmus további jellemzőjével, amely lehetővé teszi a Turing-gép számára, hogy egy adott állapotból több lehetséges jövőbeli cselekvést végezzen. A nem-determinizmus egyik megközelítése az, hogy a Turing-gép minden egyes lépésnél számos lehetséges számítástechnikai útvonalra ágyazódik, és ha bármelyik ágban megoldja a problémát, akkor azt mondják, hogy megoldotta a problémát. Nyilvánvaló, hogy ez a modell nem fizikailag megvalósítható modell, csak egy elméletileg érdekes absztrakt gép, amely különösen érdekes komplexitási osztályokat eredményez. Példákért lásd: nem determinisztikus algoritmus.