Hallo,
weil ich den anderen Thread nicht mit dieser Diskussion zuspammen möchte, mache ich hier eine neue Diskussion auf.
Was ist der Unterschied zwischen einer deterministischen Turingmaschine (DTM) und einer nichtdeterministischen Turingmaschine (NTM)?
Der Unterschied liegt in der Möglichkeit der Beschreibung einer Problemlösung (Algorithmus).
In einer DTM ist nur folgendes Szenario möglich:
Schritt 1: Tue dieses
Schritt 2: Lies jenes
Schritt 3: Tue das
Schritt 4: Tue Alternative dazu
Schritt 5: Ausgabe
Eine NTM ist ein theoretisches Konstrukt, welches noch zusätzlich die folgende Möglichkeit kennt:
Schritt 1: Tue dieses
Schritt 2: Lies jenes
Schritt 3: Entscheide nichtdeterministisch, ob nun "Tue das" oder "Tue Alternative dazu" ausgeführt werden soll
Schritt 4: Ausgabe
Gruss,
Bill