Gödelnummer / universelle Turing-maschinen ::

part of [[112.00_anchor_overview]]

Bis dato haben wir nur Turingmaschinen betrachte, welche ein einziges Program ausführen können. –> Entspricht noch lange nicht der Idee einer General Purpose Machine, also einem Konstrukt, dass jegliche Aufgaben und Probleme lösen und bewältigen kann.

Um eine Lösung des Problemes zu finden, suchen wir nun eine Sprache die hilft, eine Codierung zu implementieren:

Codierung einer TM ::

Wir definieren hier eine beispielhafte Codierung, die eine TM beschreiben kann. Diese kann man aber auch nach einem anderen Schemata erstellen, sie muss da aber diverse Bedingungen einhalten, die unten weiter / genauer definiert werden.

Sei eine TM $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$ Wir suchen nun eine Möglichkeit, um eine TM mit einem binären String codieren zu können.

Mit dieser Konstruktion haben wir die Möglichkeit diverse Zustände mit einer gegebenen Abfolge zu codieren und somit festzulegen und markieren, wann ein Bereich beginnt / beendet wird.

Sei $\Gamma$ das Arbeitsalphabet definiert mit :$\{A_1,\dots ,A_r\}$. Wir codieren jetzt jeden Buchstaben durch einen binären String:

1. Der Code $(A_j)=10^{j}1$ —> gibt eine Möglichkeit der Identifizierung von bestimmten Abschnitten!

Dieselben Codes werden wir auch füý die Buchstaben des Eingabealphabetes definieren. Das heißt : $\Sigma \subset \Gamma$

2. Weiterhin definieren wir den Zustandsraum $Q=\{q_1,\dots ,q_m\}$ wobei hier immer $q_1$ den Startzustand, $q_2$ der akzeptierende, $q_3$ der verwerfende Zustand ist. Wir können einen Zustand $i$ folgend codieren:: $Code(q_i)=110^{j}11$

3. Wir Beschreiben außerdem die Codierung zur Bewegung des Schreibkopfes folgend: $Code(L)=1110111$ –> beschreibt Bewegung nach links $Code(R)=11100111$ –> beschreibt Bewegung nach rechts.

4. Wir benötigen noch die Codierung einer Übergangsfunktion:: eine einzelne Transition wird folgend beschrieben: $Code(\delta (q,a) = ( q^{\sym},a^{\sym},B))$ wobei: $=\#Code(q)Code(a)Code(q^{}Code(a^{})Code(B))\#$

   • $\#$ wird gemäß der oberen Def codiert
   • jedes Wort wird durch seine Repräsentation mittels der Funktion $Code()$ bestimmt dargestellt.

5. Wir codieren jetzt eine ganze TM $M$ folgend: Wir müssen die TM nun mit folgenden Infos befüllen:

   • Globale Daten: Anzahl der Zustände, Anzahl $r$ der Buchsten im Arbeitsalphabet
   • eine Liste aller möglichen Transitionen, die auftreten können: Beschreiben können wir es nun wie folgt: $Code(M)=\#0^m\#0^r\#\#Code(Trans.1)\#Code(Trans.2)\#\dots$

   also ein langer String, der passend codiert eine ganze Maschine darstellt und eindeutig definiert.

   Auf diese Weise haben wir $M$ durch einen eindeutigen String über $\{0,1\#\}$ beschrieben. Da wir zuvor angegeben haben, wie etwas zu codieren ist, können wir sie in einen reinen binären String umwandeln:: dafür benötigen wir eine bijektive Abbildung: $\begin{array}{c}0⟼00\\ 1⟼11\\ \#⟼01\end{array}$ Daraus folgt folgende Codierung, beispielsweise: $001111010100$…

Unter dieser Prämisse können wir jetzt also eine TM in der Form eines Stringes beschreiben. Die Beschreibung der TM in Form eines Tupels $M=(\Sigma ,\Gamma ,\delta ,q_0,q_{acc},q_{rej})$ ist so etwas wie die Beschreibung einer höheren Programmiersprachen –> denn wir beschreiben was bei gegebenen EIngaben funktioniert, oder nicht. Der binäre Code ist eher die Beschreibung des Programmes in Maschinensprachen ::

TM : Injektivität der Codierung ::

DIe beschrieben Codierung von Turingmaschinen ist als injektiv zu beschreiben: $Code(M_1)=Code(M_2)⟶M_1=M_2$ das heißt, wenn wir zwei TMs haben, die bestimmt Codiert werden, dann sind es auch die gleichen TMs. Daraus folgt:

Jeder Code beschreibt also eindeutig eine TM

TM : Gültige / Ungültige Codes

Manche binäre Strings sind gültige Codes für eine TM. Viele binäre Strings codieren keine TM. Wir müssen irgendwie herausfinden, ob ein gegebener String gültig ist oder nicht. Anders beschrieben folgern wird: Behauptung: Es gibt eine TM $A_{g\ddot{u}ltig}$ die für einen binären String $w$ entscheidet, ob dieser eine gültige Codierung einer TM ist, oder nicht ( Sie entspricht also einer Syntaxprüfüng!) Die folgende Sprache ist entscheidbar:: $L=\{w\in \{0,1{\}}^{\ast }|\text{w ist Code einer TM}\}$

TM : Präfixfreie Codierung ::

Eine Codierung ist präfixfrei, wenn es kein Präfix in der Codierung des Codes $Code(M)$ gibt, der selbst bereits eine Codierung einer anderen TM $M^{\prime }$ ist.

Also ein Teil des Codes ist bereits die Codierung einer anderen TM, und somit haben wir eine Doppeldeutigkeit gefunden!

Diese Betrachtung ist relativ wichtig, denn : Bei einer aneinander gehängten Zeichenkette $Code(M)w$ können wir immer entscheiden, wo $Code(M)$ aufhört und $w$ anfängt. Wir müssen also auf Unterteilungen achten!

TM: Lineare Ordnung von Codierung ::

Durch die Codes können wir eine lineare Ordnung auf der Menge aller Turingmaschinen definieren:: Definition einer Linearen Ordnung: $x,y\in \{0,1{\}}^{+}$ Wir sagen dann $x\le y$, falls die natürlichen Zahlen $n_x,n_y$ die durch die jeweiligen Strings repräsentiert werden, folgende Eigenschaft aufweisen: $n_x\le n_y$ . Dann gilt $x=ϵ,y\in \{0,1{\}}^{\ast }$ und es gelte immer $ϵ\le y$.

Wir haben hier somit eine totale Ordnung auf die Menge aller binären String definiert ::

1. transitiv: $a\le b\wedge b\wedge c⟹a\le c$
2. anti-symmetrie: $a\le y\wedge y\le x⟹x=y$
3. totale Ordnung: Es gilt nur $x\le y\vee y\le x$ –> folgend aus den obigen Definitionen

Codierung einer $i$-ten Turingmaschine.

Da wir mit einem binären String unter Umständen eine Turingmaschine definieren können –> indem der String der Syntax entspricht und somit eine gültige Maschine gemäß der Codierung ist, kann man Turingmaschinen mit einem Index versehen und sie so als $i$-te Turingmaschine definieren.

Wir können einfach immer längere binäre-strings erzeugen und schauen, ob sie eine gültige Syntax aufweisen. Also $0,1,01,10,11,\dots ,0110110111000110100101\dots$

Unter dieser Betrachtung haben wir nun die Möglichkeit chronologisch alle Kombinationen durchzugehen und die $n$-te gefundene Repräsentation passend zu labeln, als die $n$-te Turingmaschine. Formaler betrachtet:: Sei $x\in \{0,1{\}}^{\ast }$. Für $i\in \mathbb{N}$ nennen wir $x$ die Codierung der $i$-ten Turingmaschine falls für diese gilt:

• $x=Code(M)$ für eine TM $M.$
• Die Menge $\{y\in \{0,1{\}}^{\ast }|y\le x\}$ enthält genau $i-1$ Wörter, die Codierungen von Turingmaschine sind. Da unsere Wörter immer länger werden, ist diese Aussage logisch folgend..

Berechenbarkeit der $i$-ten Turingmaschine:

Da wir chronologisch beschreibend Turingmaschinen in Form von Codierungen betrachten, besteht für uns die Möglichkeit diese $i$-te Turingmaschine zu berechen. Wir folgern die Behauptung: Es gibt eine TM $A$, die für ein $i\in \mathbb{N}$ die Codierung der $i$-ten TM berechnet.

Beweisidee dafür:

Die TM geht die binären Strings in der kanonischen Ordnung durch. Auf jeden String $w$ endet sie die $TM{A}_{g\ddot{u}ltig}$ um entscheiden zu können, ob $w$ die Codierung einer TM ist, oder nicht. Falls ja, erhöht sie den Zähler und wiederholt diesen Prozess, bis sie $i$ erreicht hat.

wir haben die i-te Turingmaschine in Code-form gefunden und können diese weiter folgend beschreiben:

Gödelnummer einer TM :

Ein solcher Code einer $TM$, wie wir ihn zuvor gefunden haben, wird die Gödelnummer der TM genannt.

• also eine eindeutige Beschreibung für eine bestimmte Turingmaschine
• Es ist wichtig, dass sie existiert, und dabei ist egal, wie sie gebaut wird
• Weiterhin muss sie die Injektivität erfüllen

Die Gödelnummer eienr TM wird of auch mit $⟨M⟩$ beschrieben. Intuitiv beschreibt die Gödelnummer das Programm selbst, dass von dieser Maschine $M$ durchgeführt wird.

Mann das Ganze auch formaler definieren, wann eine Codierung eine Gödelisierung ist.

Definition Gödelisierung :

Sei $M$ die Menge aller Turingmaschinen (bzw $M$ eine beliebige Sprache, die von einer TM abgearbeitet werden kann…). Dann definieren wir die Abbildung $g:M⟶\mathbb{N}$ und nennen sie Gödelisierung, falls folgende Eigenschaften erfüllt werden:

1. g ist injektiv
2. die Bildmenge $g(M)$ ist entscheidbar –> also wir können eine TM konstruieren, die für jedes n $\in \mathbb{N}$ entscheidet, ob $n\in g(M)$ gilt oder nicht.
3. Weiterhin müssen: $g:M⟶\mathbb{N}$ und $g^{-1}:g(M)⟶M$ berechenbar sein!

Gelten diese Eigenschaften, dann ist für ein beliebiges $m\in M$ $g(m)$ die Gödelnummer von der Menge $M$.

Wir haben nun diverse Turingmaschinen definiert und betrachtet, die immer nur ein Programm ausführen konnten. Aber am besten würden wir gerne eine universale Sprache definieren, die alle Sprachen verarbeiten kann. Daraus folgt anschließend auch, dass alle Turingmaschinen von dieser dargestellt werden können

Konstruktion Universeller TM ::

Wir möchten nun eine universelle TM $U$ definieren, die:

• Als Eingabe die Gödelnummer $⟨M⟩$ einer normalen TM und ein Wort $w$ erhält, wobei $w$ auf die TM $M$ angewandt werden soll

  Die UTM muss also erkennen können, ob es eine TM gibt, die eine bestimmte Eingabe verarbeiten kann und diese finden.

• U soll nun die Operation von $M$ auf $w$ simulieren, also M auf $w$ anwenden. Dabei müssen folgende Eigenschaften gelten:
  • U akzeptiert genau dann, wenn M das Wort w akzeptiert
  • U hält mit Ausgabe $x$ auf dem Band an, genau dann wenn $M$ auf $w$ das tut –> also gleiches verhalten aufweist.
• Bei einer inkorrekten Eingabe ($⟨M⟩$ ist kein gültiger Code!) gibt unsere universelle Maschine $U$ eine Fehlermeldung aus!

Wir können diese Maschine $U$ jetzt als eine $3$-Band-TM konstruieren: Dabei hat jedes Band seine Aufgabe:

1. wir simulieren das Band von $M$
2. wir schreiben die Gödelnummer $⟨M⟩$
3. merkt sich, in welchem Zustand die TM $M$ soeben wäre.

Ablauf der UTM :

Eingabe: Am Anfang steht die Eingabe $⟨M⟩w$ auf dem ersten Band geschrieben. alle anderen Bänder sind leer: ![[Pasted image 20230509142712.png]]

Vorbereitung der Maschine: Wir müssen nun einen Syntaxcheck durchführen. Dafür: U liest die Eingabe $⟨M⟩w$ auf dem ersten Band und teilt sie in die Teile $⟨M⟩$ und $w$ auf. –> In diesem Teil ist es dann wichtig, dass die Codierung präfixfrei ist! Falls $⟨M⟩$ keien korrekte Codierung ist, bricht die UTM sofort ab –> Ende. Initialisierung der Maschine: Ist die Syntaxprüfung abgeschlossen, kopiert die UTM die Gödelnummer $⟨M⟩$ auf das zweite Band und löscht sie vom ersten. Der Schreibkopf des ersten Bandes ist am Anfang von $w$. Auf das dritte Band schreiben wir die Codierung des Startzustandes $M$. ![[Pasted image 20230509142954.png]]

Simulieren eines Rechenschrittes von M::

• U weiß auf Band 3, welchen Zustand wir gerade haben
• U liest den aktuellen Buchstaben von Band 1
• U schaut auf Rand 2 nach dem zugehörigen Übergang
• U führt diesen auf Band 1 durch und merkt sich anschließend den neuen Zustand auf Band 3.

Die Ausgabe stoppt sobald auf Band 3 der akzeptierende oder verwerfende Zustand erreicht wird. Auf Band 1 steht dann die Ausgabe der berechnung, sofern existent.

Ausblick: Wir wollen folgend zeigen, dass es viel mehr Sprachen gibt, als Turingmaschinen. Daran kann man dann anschließend sehen, dass es manche Sprachen gibt, die nicht von einer TM erkannt werden können und somit TM nicht alles berechnen / entscheiden können!

Um dies richtig betrachten zu können, benötigen wir diverse Grundlagen der Mengenlehre Für weitere Informationen, siehe hier[[math1_sets]]

Größe von $$