Nicht-deterministische Turingmaschinen ::

part of [[112.00_anchor_overview]]

Notwendigkeit einer nicht-deterministischen Turing-Machine:

Betrachtet man eine normale Turingmaschine, so fallen erste Defizite auf:

• Ein- und Ausgabe und Speicher sind alle auf dem gleichen Band, wäre eine Aufteilung dieser auf getrennte Bänder sinnvoller?
• Wir können ein Band nur linear durchlaufen, und müssen sequentielle alles verarbeiten und betrachten –> wäre eine nicht-deterministische Verarbeitung nicht sinnvoller?

Äquivalenz von $N$ Turingmaschinen::

Zwei Maschinen $M_1,M_2$heißen äquivalent, falls sie die gleichen Sprachen akzeptieren. Also es muss gelten: $L(M_1)=L(M_2)$ $M_1\text{ akzeptiert w}⟺M_2\text{ akzeptiert w}$ $M_1\text{ akzeptiert w nicht }⟺M_2\text{ akzeptiert w nicht }$

Hierbei ist wichtig, dass bei der zweiten Ausgabe nicht spezifiert ist, ob die Maschinen beide das Wort einfach nicht akzeptieren oder nicht terminieren. Also eine Maschine $M_1$ kann terminieren, aber die Eingabe verwerfen und die andere $M_2$ nicht terminieren

Definition einer Nicht-Deterministischen Turingmaschine (NTM) ::

Wir könenn wie bei endlichen Automaten eine nicht-deterministische Turingmaschine definieren: Das heißt sie weist folgende Eigenschaften auf:

• Zu jedem Zeitpunkt hat die TM mehrere Möglichkeiten, wie sie fortfahren kann.
• Formal ist dann die Übergangsfunktion: $\delta :Q\times \Gamma ⟶\mathbb{P}(Q\times \Gamma \times \{L,R\})$
• Eine Berechnung der NTM entspricht dann einem Pfad im Baum aller möglichen Pfade, die die Turingmaschine nehmen könnte.

Da Turingmaschinen theoretisch unendlich lange laufen können, gibt es auch unendlich Äste in diesen Bäumen

Berechnung einer NTM :

Eine Berechnung einer NTM entspricht einem möglichne Pfad im Baum aller möglichen Berechnungen der NTM.

Dabei ist dann eine Berechnung akzeptierend / verwerfend, falls sie in einem azkeptierenden/verwerfenden Zustand endet.

Weiterhin besteht die akzeptierte Sprache aus den Wörtern, für die eine akzeptierende Berechnung existiert:

• Also mindestens einer der Pfade im Berechnungsbaum endet irgendwann im akzeptierenden Zustand

==Ein Pfad im Baum== kann akzeptierend sein, während es gleichzeitig Pfade gibt, die nicht terminieren oder sogar in einem verwerfenden Zustand enden.

Wir haben jedoch nicht definiert, was es heißt, dass eine NTM verwirft oder nicht anhält. –> In der Betrachtung können wir sagen: Dass ein NTM ein Wort verwirft, wenn alle Pfade im verwerfenden Zustand enden. Denn finden wir einen akzeptierenden Zustand, dann ist das Wort wieder akzeptiert!

Äquivalenz von $N$ NTM / DTM :

Wie obig bereits betrachtet herrscht eine Äquivalenz zwischen zwei Turing-maschinen, wenn sie die selbige Sprache $M$ erkennen und repräsentieren können.

Ferner unter Betrachtung von Nicht-Deterministischen Turing-Maschinen können wir sagen:

Zu jeder NTM (NichtDeterministische Turing-Maschine) $N$ gibt es eine DTM(Deterministische Turing-Maschine) $D$ so, dass folglich gilt: $L(N)=L(D)$

Wir sprechen bei DTMs von nicht akzeptierend / verwerfend $\vee$ nicht terminierend, was Begriffe sind, die wir in einer Nicht-Deterministischen Turing Maschine bis dato noch nicht betrachtet haben: Wir können hier einfach durch logische Umformung eine Definition aufbauen:

$N\text{ akzeptiert}w\text{ nicht}$ : $⟺\neg (N\text{ akzeptiert }w)$ $⟺\neg \exists \text{Pfad}:\text{ Pfad akzeptiert }$ $⟺\forall \text{ Pfade }\neg (\text{ Pfad akzeptiert })$ $⟺\forall \text{ Pfade}:\text{ Pfad verwirft oder endet nicht}$

Wir haben zuvor schon bewiesen, dass deterministische und nichtdeterministische endliche Automaten äquivalent sind.

Beweisidee DTM $=$ NTM :

Wir können jetzt ein ähnliches Prinzip anwenden, um die Äquivalenz von DTM und NTM zu beweisen:

Dafür betrachten wir den Berechnungsbaum unseres NTM: ![[Pasted image 20230504130321.png]] Diesen können wir jetzt mit einer Breitensuche betrachten und Schicht für Schicht nach einem akzeptierenden Zustand für unser Wort $W$ suchen. Sobald wir einen Akzeptierenden Zustand finden, dann wirld also gelten: $N\text{ akzeptiert }w⟺D\text{ akzeptiert }w$

Wichtige Folgerung aus Äquivalenz von NTM und DTM ::

Wir haben jetzt gezeigt, dass unter Betrachtung der ==Berechenbarkeitstheorie== DTMs äquivalent zu NTMs sind. Also wir können mit beiden die selbige Sprachen erkennen und lesen. Was wir dabei jedoch nicht festlegen, ist der Aspekt, dass NTMs unter Umständen schneller und effizienter arbeiten können.

Das heißt eine NTM ist somit nicht Komplexitäts-Äquivalent zu einem DTM!

Weiter mit [[theo2_SprachenEntscheidbarkeit]]