Turing-Maschinen und Berechenbarkeitstheorie:

part of [[112.00_anchor_overview]]

Zuvor haben wir diverse Automaten [[112.09_kellerautomaten]],[[112.04_non_deterministische_automaten]] betrachtet, welche mit limitierten oder keinem Speicher viele Sprachen nicht erkennen können. Um das zu erweitern, wollen wir eine allgemeinere Struktur eines Computers definieren:

• Kann eine Eingabe lesen
• hat beliebig viel Speicherplatz –> Turing!
• kann DInge an beliebigen Stellen in den Speicher schreiben und wieder auslesen
• kann beliebig viele Rechenschritte machen

Wir simulieren hier also einen Computer welcher einen Speicher - RAM / Memory - aufweist, welcher aber sehr linear aufgebaut ist. Da unsere Maschine in ihren Übergangsfunktionen beliebig entlang des Bandes agieren kann, besteht die Möglichkeit, damit alle Routinen und Abläufe beschreiben zu können. Das ist gegeben, da wir als eine Betrachtung prinzipiell unendlich viel Speicher haben.

Intuitive Definition Turingmaschine ::

![[Pasted image 20230504102047.png]]

Als Grundstruktur haben wir also einen linearen Speicher gegeben, welchen wir beliebig beschreiben bzw. modifizieren können.

Zu Beginn einer Berechnung steht die Eingabe auf dem Band - also die Eingabe wurde als Form von Symbolen auf dem Band geschrieben - und wir können diese später mit dem Lesekopf betrachten, bearbeiten und auch löschen. Der Startzustand ist dabei mit $q_0$

Als grundlegende Charakteristik hat eine Turingmaschine also:

• den Inhalt des Bandes zur Verfügung
• die Position des Lese- / Schreibkopfes –> dieser kann sich frei bewegen!
• den derzeitigen Zustand $\in Q$

In jeder Konfiguration macht die TM das Folgende:

• Sie liest das Symbol an der Stelle, wo der LEse- / Schreibkopf gerade steht.
• Sie schaut in ihrer Übergangsfunktion nch, was sie im derzeitigen Zustand bei Lesen dieses Symbols tun soll :
  • Sie kann im derzeitigen Feld ein neues Symbol schreiben (das alte wird dabei überschrieben)
  • sie kann den Lese- / Schreibkopf nun ein Feld nach links oder rechts bewegen.
  • sie kann nach dem Einlesen gemäß der Übergangsfunktion ( ihr derzeitiger Zustand etc) in einen neuen Zustand übergehen.

2 Endzustände:

DIe Turing-Maschine kann entweder an einem Endzustand ankommen und hält dann an, die TM terminiert und die Verarbeitung ist abgeschlossen.

Sofern die TM aber keinen Endzustand erreicht und weiter rechnet, dann ist das ein Indikator, dass sie nicht terminiert und somit immer weiter rechnen wird. Sie terminiert nicht!

Beispiel :::

Formale Definitino Turingmaschine :

Eine Turingmaschine ist ein 7-Tupel $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$: wobei:

• $Q$ eine endliche Menge von Zuständen ist
• $\Sigma$ ist eine endliche Menge, das Eingabealphabet
• $\Gamma$ ist eine endliche Menge, das Arbeitsalphabet, mit $\Sigma \subset \Gamma$ und einem Leerzeichen __ $\in \Gamma$
• $\delta :Q\times \Gamma ⟶Q\times \Gamma \times \{L,R\}$ die Übergangsfunktion, die immer den vorhandenen Specher aus dem Arbeitsalphabet, dem Eingabealphabet betrachtet
• $q_0\in Q$ der Startzustand unsere Automaten
• $q_{accept}\in Q$ der akzeptierende Endzustand
• $q_{reject\in }Q$, $q_{reject}\ne q_{accept}$ der verwerfende Endzustand

Es gibt genau einen akzeptierenden und einen verwerfenden Zustand.

DIe TM beendet ihr Berechnung sobald sie einen dieser beiden Zustände erreicht. (Sie kann auch nicht beenden, dann terminiert sie nicht und wird für immer weiterlaufen. nicht-terminierend) Das Band der TM hat ein linkes Ende und ist nach rechts unbeschränkt: Zumindest unter Betrachtung unseres Modelles ist sie nach links beschränkt, es ist auch möglich, dass sie in beide Seiten unbeschränkt ist, aber das ist trivial bzw wird sich die Mächtigkeit nicht verändern! Es ist wichtig, dass eine Turingmaschine endlich viele Zustände aufweist, auch wenn sie unendlich viel Speicher hat!

Beispiel: Erkennen von Zweierpotenzen

Wir wollen eine TM bauen, die die Sprache $L=\{(0^2{)}^n|n\in {\mathbb{N}}_0\}$ erkennen kann.

Die Idee hier: Lies von Links nach rechts und streiche jede zweite 0 Weg. Dabei

• Wenn es nur eine 0 gibt, dann accept –> Erfüllte Kondition
• Wenn es mehr als eine 0 gibt und die Anzahl ungerade ist reject !
• Wenn die Anzahl gerade war, fang wieder von vorne an –> weitere Reduktion!

Ein Möglicher Automat könne so aussehen:: ![[Pasted image 20230504105411.png]]

Konfiguration der Turing Maschine ::

Eine Konfiguration der TM $M$ wird beschrieben durch den Inhalt des Bandes, die Position des Lesekopfes und den derzeitigen Zustand $q\in Q$ . In kompakter Notation wird das wie folgt aufgeschrieben: –> $uqv$
Dabei ist:

• Inhalt des Speicherbandes ist der String u und v
• Position des Schreibkopfes ist direkt nach $u$, auf dem ersten Buchstaben von $v$
• der Zustand ist $q$

Wir können damit also eine grafische Darstellung einfach niederschreiben: ![[Pasted image 20230504105914.png]] Diese grafische SChriebweise können wir folgend darstellen: $0101q_{7}111$

Berechnung der Turing-Maschine ::

Eine Berechnung der TM $M$ auf einer Eingabe $w$ ist eine gültige Folge von Konfigurationen $C_0,C_1,C_2,\dots$ so, dass $C_0$die Startkonfiguration ist und die Konfiguration $C_{i+1}$ jeweils in der Übergangsfunktion beschrieben aus $C_i$ hervorgeht.

EIne Berechnung einer $TM$ auf Eingabe $w$ heißt dann entweder:

• akzeptierend falls sie im Zustand $q_{a}ccept$ endet oder
• verwerfend falls sie im Zustand $q_{reject}$ endet.

Weiterhin heißt eine Berechnung nicht-akzeptierend, falls sie entweder mit:

• $q_{r}eject$ endet
• oder nie beendet wird

Außerdem: Die von der TM $M$ akzeptieret Sprache L(M) istdie Menge der Wörter, die von M akzeptiert werden.

Wenn wir ein Wort $\notin L$ haben, dann kann die TM entweder verwerfen oder nie anhalten

rekursiv aufzählbar ::

Auch mit Sie wird akzeptiert beschrieben:

Eine Sprache $L$ heißt rekursiv aufzählbar bzw (semi-entscheidbar), falls es eine TM M gibt, die $L$ akzeptiert. Das heißt also:

• $w\in L⟹M$ akzeptiert w,
• $w\notin L⟹M$ verwirft oder hält nicht an.

(rekursiv) entscheidbar ::

Auch mit Sie wird von einer TM entschieden beschrieben:

Eine Sprache $L$ heißt (rekursiv) entscheidbar, falls es eine TM $M$ gibt, so dass gilt:

• $w\in L⟹M$ akzeptiert w,
• $w\notin L⟹M$ verwirft w.

unsere TM $M$ hält hier immer an!

Es kommen so diverse Fragen auf :

Wie mächtig ist das Modell der TM?

• Welche Sprachen werden von einer TM erkannt?
• WIe siet die Menge der rekursiv aufzählbaren Sprachen und der entscheidbaren Sprachen aus?
• Sind die beiden Mengen identisch oder nicht?
• Gibt es Sprachen, die weder das eine noch das andere sind?

–> DAS Meiste werden wir mit der Berechenbarkeitstheorie abdecken.

WIe realistisch / allgemeingültig ist das Modell der TM ?

• Können TMS wirklich das Gleiche wie normale Computer?
  • Oder sind sie zu eingeschränkt?
• Gibt es weitere Berechnungsmodelle oder vielleicht auch ganz komplett ander Modelle, von denen man andere Dinge beweisen kann? –> muss alles über Sprachen gehen?

Weitere Variante ::

Man kann sich noch viele weiter Varianten von deterministischen Turingmaschinen ausdenken. Am Ende stellt sich hier aber heraus, dass die meisten davon äquivalent sind und ihre Mächtigkeit gleich ist :

• Es ist egal, ob wir jedes Alphabet zulassen oder nur binäre
• diverse Mengen von Bändern sind möglich, aber durch die Unendlichkeit trivial
• Wir können dem Schreibband random access gewährleisten ::

unter weiterer Betrachtung gibt es auch nicht deterministische TMs: ![[112.13_turing_maschinen_nondeterministisch]]