date-created: 2024-05-16 10:26:05 date-modified: 2024-09-22 04:03:40

Turing Maschinen | Speicherbasierte Rechenmodelle

For non-deterministic Turing-machines look at: non deterministic turing machine

Overview

Wir wollen uns von deterministischen / nicht deterministischen Automaten entfernen und nun ein mächtigeres - sogar das mächtigste - system bzw. Konstrukt einer Rechenmaschine

Grundlage

Turing-Maschinen operieren auf einem Band welches eine unendliche Länge aufweist und hat. Dabei ist es ähnlich konzipiert, wie ein Automat mit Speicher, welcher hier aber theoretisch unendlich ist.

Ablauf: Wenn wir jetzt den Automaten nutzen, dann beginnt er am linken Ende des Bandes. Dabei ist die Eingabe, die wir tätigen möchten, stets bereits auf dme Band aufgetragen. Wir schauen uns dann also Schritt für Schritt die Eingabe an.

Hierbei ist wichtig, dass bei jedem Schritt die Maschine ein Symbol auf den Band am Schreib-Lesekopf

Beispiel

Betrachten wir die Sprache, die folgende Sprache erkennen kann: $L=\{w\#w\mid w\in \{0,1{\}}^{\ast }\}$ (also zweimal der gleiche String mit einem # getrennt)

[!Intuition] Wir wollen immer den ersten Buchstaben einlesen, uns merken, und dann an der rechten Stelle nach dem trennenden Wort wieder schreiben

Wir lesen also den ersten Buchstaben in der Eingabe

setze eine Markierung, damit man später wieder ankommen und weitermachen kann:

gehe jetzt so weit nach rechts, bis wir # überschritten und das erste mal nicht das markierende Wort $X$ gelesen haben (ein unberührtes Wort)

Jetzt überschreiben wir es mit $X$ und gehen wieder nach links bis zu $X$

Das ist die Grundidee, man kann sie aber auch nochmal formaler mit dem Tupel und der Übergangsfunktion beschreiben:

[!Tip] Stringcomparison als Turing-Maschine Definiere die TM: $M=(Q,\Sigma ,\Gamma ,\delta ,q_1,q_{accept},q_{reject})$

• $Q=\{q_1,\dots ,q_8,q_{accept},q_{reject}\}$
• $\Sigma =\{0,1,\#\}$
• $\Gamma =\{0,1,\#,⊠,x\}$

Und die Übergangsfunktion können wir folgend beschreiben:

Siehe auch Sipser, EX 3.9

Definition

Wir wollen ferner die Turing-Maschine jetzt formal beschreiben und definieren:

[!Definition] Turing-Maschine $M$

Die Turing Maschine wird mit einem 7-Tupel beschrieben und definiert.

welche Sieben Attribute muss sie demnach aufweisen? #card

Die Turing-Maschine wird folgend beschrieben: $$\begin{array}{rl}>M:& =(Q\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})>\end{array}$$ Wobei wir die einzelnen Zustände folgend beschreiben wollen:

• $Q$ ist eine endliche Menge von Zuständen
• $\Sigma$ ist eine endliche Menge, und beschreibt das Eingabealphabet - wie immer
• $\Gamma$ ist eine endliche Menge und beschreibt das Arbeits und Bandalphabet, wobei hier $\Sigma \subseteq \Gamma$ und weiterhin beschreiben wir ein neues Symbol $⊠\in \Gamma$ Was angibt, ob wir die TM überschreiben
• Die Übergangsfunktion $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$
• Ferner beschreibt: $q_0\in Q$ den Startzustand
• $q_{accept}\in Q$ ist der akzeptierender Zustand
• $q_{reject}\in Q$ mit $q_{accept}\ne q_{reject}$ ist der verwerfende Zustand!

[!Tip] Bemerkungen und Konzepte der Turing-Maschine Es gibt genau einen akzeptierenden und genau einen verwerfenden Zustand bei Turingmaschinen!

Turing-Maschinen beenden ihre Rechnung sobald sie einen der beiden Zustände - akzeptierend / verwerfend! –> Man nennt das dann halten

Die Turing-Maschine hat hier ein linkes Ende. Wenn die Maschine da steht und durch eine Operation - der Übergangsfunktion - gefordert wird, dass man nach links gehen solle, dann bleibt der Kopf am linken Ende stehen.

Formal definiert bedarf es jetzt noch einer Betrachtung der Berechnung und Konfiguration einer entsprechenden Turing-Maschine.

Konfiguration / Berechnungen

Sprechen wir von der Konfiguration einer Turing-Maschine, dann beschreiben wir hiermit ein 3-Tupel was uns angibt, wo sich der Lesekopf befindet, welchen Zustand wir soeben haben und was der Inhalt des Bandes ist, wobei wir den Wert links und rechts vom Lesekopf beschreiben.

Also kurz definiert:

[!Definition] Konfiguration einer TM Wir beschreiben die Konfiguration einer Turing-Maschine folgend mit einem “Tupel” $uqv$

was wird mit diesem Tupel beschrieben? #card

$u$ beschreibt den Inhalt links vom Lesekopf $v$ beschreibt den Inhalt rechts vom Lesekopf $q$ ist der aktuelle Zustand $\in Q$

Wir möchten jetzt den Übergang eines Zustandes in einen anderen beschreiben und dabie also zwei Konfigurationen betrachten und evaluieren, wie man von den einen zum anderen kommen kann.

[!Satz] Übergang zwischen Konfigurationen

Wir sagen dann die Konfiguration $C_1$ geht über $C_2$, wenn die Turing-Maschine folgend von einem Schritt $C_1$ zu einen neuen Schritt $C_2$ wechseln kann. Genauer sei dann demnach $a,b,c\in \Gamma$ und weiter auch $u,v\in {\Gamma }^{\ast }$ und auch $q_i,q_j\in Q$ ( was der Nachfolge Bereich ist)

was gilt dann für die Übergangsfunktion #card

Wir können damit jetzt die Übergangsfunktion folgend beschreiben / definieren: $$\delta (q_j,b)=\{\begin{array}{ll}>(q_j,c,L)& \text{ dann geht }{C}_1=uaq,bv\text{ u¨ber in }{C}_2=u{q}_j,acv\\ >& q_{i}bv\text{ geht u¨ber in }{q}_{j}cv\text{ das ist der Sonderfall im linken Bandende}\\ >& \text{ und}ua{q}_i=uaq,\to ⊠\text{ geht u¨ber in }u{q}_{j}ac\text{ was dann den Sonderfall rechtes Bandende}\\ >(q_j,c,R)& \text{ dann geht }{C}_1=ua{q}_{i}bv\text{ u¨ber }{C}_2=uac{q}_{j}v\\ & \text{und }{q}_{i}bv\text{ geht u¨ber in }c{q}_{j}v\text{ Sonderfall linkes Bandende}\\ & \text{ und}ua{q}_i=ua{q}_i\to ⊠\text{ geht u¨ber in }uac{q}_j\to ⊠\text{(Sonderfall rechter Bandrand)}>>\end{array}$$

Die Startkonfiguration der Turing-Maschine $M$ auf einer beliebigen Eingabe $w$ ist dabei mit $q_{0}w$ beschrieben!

Ferner nennen wir eine Konfiguration $q=q_{accept}$ akzeptierende Konfiguration. Das heißt also, dass der derzeitige Zustand jetzt der akzeptierende ist und wir somit abschließen können - die Inhalte / links/rechts davon sind somit nicht mehr relevant. Analog gilt das auch für die verwerfende Konfiguration.

[!Attention] Beide Konfigurationen benennen wir am Ende als haltende Konfigurationen

Berechnung einer Turing-Maschine

Nachdem wir nun die Konfiguration einer Turing-Maschine definiert haben, können wir ferner darauf eingehen, wie man jetzt eine Berechnung - also Ablauf von Konfigurationen und somit Verarbeitung einer Eingabe - darstellen / definieren.

[!Definition] Berechnung einer Turing-Maschine Gegeben ist eine Turing-Maschine $M$ und ferner eine Folge von Konfigurationen $C_1,C_2,\dots ,C_k$ sodass jetzt folgen wird: wie können wir jetzt eine Berechnung unter Betrachtung der Konfigurationen definieren? #card

1. $C_1=q_0,w$ -> also die Folge beginnt in der gegebenen Startkonfiguration
2. $C_i$ geht über in $C_{i+1}$ -> also genau der Übergang in der Konfiguration, wie obig definiert und das gilt $\forall i\{1,\dots ,k-1\}$ Konfigurationen

Resultate Falls $C_k$ jetzt akzeptierend ist, heißt dann die Folge von Konfigs eine akzeptierende Berechnung und wir nennen die $M$ akzeptierend für Wort $w$! Falls $C_k$ jetzt verwerfend ist, dann nennen wir die Folge verwerfende Berechnung und wir sagen, dass $M$ das Wort $w$ verwirft.

Sonderfall Wenn wir jetzt ein Wort betrachten wo wir eine Konfiguration $C_k$ erhalten, welche nicht verwirft oder akzeptiert $\forall k$, dann nennen wir diese Folge nicht-haltend. Wir sagen dann folgend $M$ hält nicht auf $w$

Sprachen von Turingmaschinen

Wir möchten wieder definieren, welche Sprachen mit Turingmaschinen beschrieben, erzeugt und erkannt werden können.

Wir werden später sehen, dass es einen Unterschied zwischen entscheidbar und erkennbar gibt, der sehr fundamental und wichtig ist!

[!Definition] Sprachen einer Turingmaschine

Die Menge aller Worter $w\in {\Sigma }^{\ast }$ welche von einer Turingmaschine $M$ akzeptiert werden, bilden die von $M$ erkannte Sprache $L(M)$ Wir beschreiben sie also mit : $L(M):=\{w\in {\Sigma }^{\ast }\mid M\text{ akzeptiert }w\}$

wann nennen wir eine Sprache jetzt erkennbar, rekursiv aufzählbar oder semi-entscheidbar? #card

Sofern wir eine TM beschreiben können, die eine Sprache $L$ erkennt, sprechen wir von Turing-erkennbar, rekursive aufzählbar, oder semi-entscheidbar. Wir beschreiben die Eigenschaft der Erkennbarkeit folgend für Wörter $\in {\Sigma }^{\ast }$ :

• wenn $w\in L⟹$ dann akzeptiert $M$ $w$, also nach einer Eingabe wird sie terminieren und in den akzeptierenden Zustand gehen!
• wenn jetzt $w\notin L⟹$ dann verwirft $M$ oder hält nicht auf $w$ (also läuft endlos weiter)

Ferner möchten / müssen wir auch die Charakteristik einer entscheidbaren Sprache definieren.

[!Definition] Entscheidbare Sprachen

Die Menge aller Wörter $w\in {\Sigma }^{\ast }$ auf welchen die TM hält (also akzeptiert/verwirft) bilden dann die von M entschiedene Sprache.

wann nennt man eine Sprache jetzt Turing-entscheidbar,rekursiv oder der Länge aufzählbar? #card

Wir nennen eine Sprache $L$ turing-entscheidbar, rekursiv, oder der Länge nach aufzählbar, wenn es eine TM $M$ gibt, welche sie entscheiden kann (also für jedes Wort hält!)

Die TM $M$ ist dann ein Entscheider für $L(M)$. Das heißt es können zwei Zustände eintreten:

• wenn $w\in L⟹$ $M$ akzeptiert $w$
• wenn $w\notin L⟹$ $M$ verwirft $w$

[!Req] Unterschied Entscheidbar / Erkennbar

Wo liegt der Unterschied zwischen einer entscheidabren und erkennbaren Sprache, Was gilt auch aus “Mengenbetrachtung”? #card

Wir sehen hier, dass eine erkennbare Sprache “schwächer” ist, als eine entscheidbare, weil bei letzterer eine Eingabe einfach nicht zum Ende führen kann -> und wir so vielleicht nicht wissen, ob sie das Wort noch akzeptieren kann/wird oder nicht.

Währenddessen werden die Wörter einer entscheidbaren Sprache für eine TM $M$ garantiert akzeptiert oder verworfen. (Sie hält also immer!)

Weiterhin ist jede Turing-entscheidbare Sprache natürlich auch Turing-erkennbar.

Die Rückkehr gilt aber nicht: nicht jede erkennbare Sprache ist auch entscheidbar!

Turingmaschinen und Automaten

[!Satz]

Es gilt: Jeder DFA ist ein Spezialfall einer Turingmaschine

Wie können wir das zeigen? #card

Wir konstruieren ferner eine Turingmaschine, die das Tupe; eines DFa konvertiert: $$M:=\underbrace{Q,\Sigma ,{\delta }_F,q_0,F}\text{ Struktur DFA}=(Q,\Sigma ,\Gamma ,{\delta }_T,q_{accept},q_{reject})$$ wobei wir jetzt folgend anpassen:

• $\Gamma =\{\Sigma \cup \{⊠\}\}$
• ${\delta }_T(q,a)=({\delta }_F(q,a),a,R)$
• $${\delta }_T(q,⊠)=\{\begin{array}{ll}>(q_{accept},⊠,R)& \text{ falls }q\in F\\ >(q_{reject},⊠,R)& \text{ sonst}>\end{array}$$

Dass wir diese Turingmaschine entsprechend konvertieren können lässt uns auch folgern:

[!Korollar]

Alle DFAs sind Entscheider und alle Sprachen in $REG$ sind auch entscheidbar 112.03_reguläre_sprachen

Äquivalenz von $N$ Turingmaschinen:

[!Definition] Äquivalenz von Turing-Maschinen

Zwei Maschinen $M_1,M_2$heißen äquivalent, falls sie die gleichen Sprachen akzeptieren. Also es muss gelten:

Welche drei Eigenschaften müssen erfüllt werden? Was folgt noch? #card

$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 spezifiziert 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

Syntaktischer Zucker

Folgend können wir einige Variationen der Turing-Maschine als Konzept betrachten, welche allesamt gleichmächtig/wertig, wie die normale Turingmaschine sind, aber u.U. dabei helfen manche Themen oder Beweise besser zu führen!

Bewegungen des Schreibkopfes

Es ist möglich statt der Urdefinition, die nur Bewegungen nach links/rechts erlaubt, auch eine “verweilende Bewegung (stehen bleiben)” zu begründen.

[!Req] Erlauben des “stehen bleibens”

Wir können erlauben, dass der Schreibkopf nach Einlesen eines Symboles auch einfach stehen bleibt und damit weiterhin richtig funktioniert. Wir wollen also den Übergang folgend um die Bewegung $S$ = “still” erweitern: statt ${\delta }^{\prime }:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ also nun ${\delta }^{\prime }:Q\times \Gamma \to Q\times \Gamma \times \{L,S,R\}$

wie können wir das konstruieren? #card

Das können wir erzielen, indem wir die Zustände verdoppeln, also $Q^{\prime }=\underset{\text{ Zusta¨nde der normalen TM}}{\underbrace{[q_0,\dots ,q_n.q_{accept},q_{reject}]}}\cup \underset{\text{ neue Zwischenzusta¨nde}}{\underbrace{[q_0^S,\dots ,q_n^S.q_{accept}^S,q_{reject}^S]}}$

Ferner erweitern wir dann die Übergangsfunktion folgend:

$$\begin{array}{ll}>\text{ Falls }\delta (q_i,a)& =(q_j,b,R)\\ >\text{ oder }& =(q_j,b,L)>\end{array}\}\text{ dann: }{\delta }^{\prime }(q_i,a)=\delta (q_i,a)$$

Falls ferner $\delta (q_i,a)=(q_j,b,S)$ dann formen wir um zu ${\delta }^{\prime }(q_i,a)=(q_j^S,b,R)$ und weiterhin fügen wir ein: $\forall x\in \Gamma$ : ${\delta }^{\prime }(q_i^S,x)=(q_i,x,L)$

Wir haben sie also so erweitert, dass sie bei einem gewollten $S$ Übergang immer in den äquivalenten $q^S$ Überstand geht (nach rechts geht) und anschließend zum Ziel (und dabei nach links geht).

Dann ist offensichtlich die $M^{\prime }$ TM mit ${\delta }^{\prime }$ äquivalent zu $M$ mit $\delta$, weil die Konfigurationen von $M^{\prime }$ die von $M$ mit einem Zwischenschritt ist / sind.

Die Grafik ausgeschrieben ist dann: $M:xcqay\to xcrby$ über, und die angepasste Turingmaschine $M^{\prime }$ geht folgend über: $xcqau\to xcb{r}^{S}y\to xcrby$

Mehrband-Turingmaschinen

[!Definition] Mehrband-Turingmaschinen

Eine Mehrband-Turing-Maschien ist eine normale TM mit endlich vielen Bändern.

wie definieren wir eine Mehrband-Turingmaschine? #card

Prinzipiell ist es eine normale TM, aber mit mehreren Bändern.

Dadurch ändert sich primär die Definition der Übergangsfunktion!

Jedes Band hat seinen eigenen Lese/Schreibkopf die sie denoch eine gemeinsame Zustandsmenge $Q$ teilen -> somit bleibt diese Konstruktion gleich.

Zu Beginn, also $q_0$ steht die Eingabe auf dem ersten Band und die anderen sind leer

Formal hat sie dann eine neue Übergangsfunktion der Form: $$\delta :Q\times {\Gamma }^k\to Q\times {\Gamma }^k\times \{L,S,R{\}}^k$$ wobei wir mit $k$ angeben, wie viele Bänder und somit wie viele weitere Inhalte man betrachten muss, um entsprechend weiterzulaufen

$$\delta (\underset{\text{ aktueller Zustand}}{\underbrace{q_i}},\underset{\text{ gelesen auf allen Ba¨ndern}}{\underbrace{a_1,\dots ,a_k}})=(\underset{\text{ neuer Zustand}}{\underbrace{q_j}},\underset{\text{ schreiben auf alle Ba¨nder}}{\underbrace{b_1,\dots ,b_k}},\underset{\text{ Bewegung aller Ko¨pfe}}{\underbrace{L,S,\dots ,R}})$$

Wir sehen aber trotzdem, dass Parallelismus nicht helfen kann / wird!

Parallelismus hilft nicht

[!Satz]

Zu jeder Mehrband-TM gibt es eine äquivalente Einband-TM

wie können wir das beweisen? #card

Sei jetzt $M$ eine $k$-Band TM. Wir konstruieren nun die Einband TM $S$ so, dass $L(M)=L(S)$ ist / ergibt.

Die Idee dafür: Speichere den Inhalt aller Bänder hintereinander auf dem Band von $S$. Wir trennen sie durch ein Sonderzeichen $\#$ voneinander.

-> Wir markieren dann immer die aktuelle Position der verschiedenen Schreibköpfe durch einen “punkt” (oder einer anderen Markierung) $\dot{(}a)$ –> damit haben wir $\Gamma$ erweitert. Visuell also:

Formaler Beweis: Wir wollen die Einband TM $S$ konstruieren.

Sei dafür eine Eingabe $w=w_1,\dots ,w_n$

$S$ geht in die Konfiguration: $\#{\dot{w}}_1,w_2,\dots w_n\#\dot{⊠}\#\dot{⊠}\#\dots ,\#$

Wir wollen jetzt einen Schritt von $M$ auf $S$ simulieren:

• fährt $S$ das ganze band ab - vom ersten $\#\to {\#}^{k+1}$ um somit alle Symbole unter den $k$ Schreibköpfen zu lesen! –> Sie werden durch eine endliche Erweiterung des Zustandraumes gecached (also wir haben extra Zustände, die diese Werte dann “speichern”)
• macht dann einen zweiten Lauf entlang des Bandes um die $k$-Köpfe Einträge entsprechend der Übergangsfunktion zu aktualisieren
  • –> der nötige “Zwischenspeicher” wird durch eine erweiterte Zustandsmenge realisiert
• Wir haben ferner einen Spezialfall: Falls in einem Schritt einer der Köpfe von $M$ am Ende des $j$-ten Bandes ankommt, also wir danach “leere Elemente treffen würden”, dann fahren wir ans gesamte Ende der TM $S$ und verschieben ferner alle Symbole nach diesem Bereich nach rechts (machen also entsprechend Platz)

Dadurch erhalten wir eine valide Reduzierung ( auch wenn sie sehr komplex ist)

Beidseitig offene Bänder

[!Satz]

Sei $M_L$ eine TM, die beidseitig offene Bänder hat ( also man endlos nach links und rechts kann), dann gibt es eine TM $M$ mit links abgeschlossenem Band, sodass $M$ äquivalent zu $M_L$ ist

was wäre ein Beweisansatz? #card

Man könnte hier abwechselnd ein Feld auf dem Band der “linken Hälfte” und der “rechten Hälfte” zuordnen und somit realisieren

Etwa durch “Gerade => links, Ungerade => rechts”

Nicht-Deterministische Turing-Maschinen

Siehe 112.13_turing_maschinen_nondeterministisch

NTM $\equiv$ DTM sind also gleich

[!Definition]

Es gilt: Zu jeder nichtdeterministischen TM $N$ gibt es eine äquivalente deterministische TM $D$!

wie können wir das konstruieren? #card Wir konstruieren also eine Mehrband-TM $D$, die NTM auf der Eingabe $w=w_1,\dots w_n$ simuliert (en kann)

Konstruktion von drei Bändern:

• eins ist Eingabe
• eins ist RAM –> es speichert uns die soeben passierende Berechnung, also die aktuelle Konfiguration, weil wir ja dann nicht-deterministisch durch diese alle verschiedenen Möglichkeit laufen können und somit simulieren wir den Ablauf der nicht deterministischen Turing Maschine
• drittes Band gibt an, wo wir uns im Baum befinden.

Berechnung:

1. Initialisiere mit $w$ auf Band 1, und leeren Bändern 2,3
2. Kopiere $w$ auf Band 2, initialisiere 3 mit $\epsilon$
3. Simuliere den Lauf von $N$ auf Band 2. Schaue dazu in jedem Schritt auf Band 3 nach, welche Option zu nehmen ist.
4. Falls auf Band 3 nichts mehr steht oder der Pfad auf Band 3 ungültig ist, gehen wir zum vierten Schritt!
5. Falls $q_{reject}$ erreicht wurde, gehen wir zum vierten Schritt
6. Falls $q_{accept}$ erreicht wurde, akzeptieren wird!
7. Ersetze den Pfad auf Band 3 mit seinem Nachfolger - > in der natürliche Anordnung dieser Strings
8. Simuliere dann den nächsten Pfad wie zuvor, also von Schritt 2 an

Wir wollen den Baum der Zustände - des Nicht Deterministischen Automaten - nach und nach traversieren und dann Breadth-First durch diesen laufen. Damit decken wir alle Fälle ab und wenn wir in einem Baum einen “accept” finden, dann akzeptieren wir.

Sonst lehnen wir ab!

Was kann eine Turing-Maschine?

[!Bem] Turingmaschinen als abstrakte Operatoren

Bevor wir uns der universellen Darstellung und weiteren Betrachtungen zur Turing-Maschine widmen, möchten wir Zwischenfragen stellen, die beim Verständnis und Betrachten helfen können.

–> weswegen nennen wir Turing-erkennbare Sprachen - rekursiv Aufzählbar?

-> Wie hängen die Konzepte von Erkennbarkeit und Entscheidbarkeit zusammen - gerade im Bezug auf tatsächliche Systeme, die meist nur entscheidabre Informationen bearbeiten/berechnen etc

-> Kann man Turing-Maschinen programmieren?

Warum rekursiv aufzählbare Sprachen?

Dafür möchten wir einen Enumerator (Aufzähler) definieren:

[!Definition] Enumerator ( Aufzähler)

Wir bezeichnen eine TM mit Drucker einen Enumerator ( Aufzähler) mit einem 7-Tupel mit folgender Struktur : $E=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{print},q_{stop})$

Visuell geht der Enumeator durch alle Wörter der Kleensche-Hülle druckt aber nur die Wort aus, die von der Turing-Maschine erfüllt wird.

Was geben uns die einzelnen Aspekte aus, was ist die Erweiterung zu einer normalen TM? #card

Sie weist folgende Parameter auf:

• $Q$ ist eine endliche Menge von Zuständen
• $\Sigma$ ist eine endliche Menge, das Ausgabe- oder Druckalphabet
• $\Gamma$ ist eine endliche Menge, das Arbeits oder Bandalphabet
• die Übergangsfunktion ist nun etwas anders: ( bzw sieht gleich aus, aber funktioniert noch anders) $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}\times {\Sigma }_{\epsilon }$
• ferner $q_{print}$ der Druckzustand, und $q_{stop}$ der Haltzustand, wobei $q_{print}\ne q_{stop}$

Die Konfigurationen und Übergänge von $E$ sind die der Turingmaschine, mit dem Zusatz, dass $E$ in jedem Schritt ein Zeichen auf das Druckband schreiben kann ( also ausdrucken!). Wir schreiben dann etwa für $(uaqbv)(x)$ folgende Konfiguration

“$E$ ist im Zustand $q$, links vom Kopf steht gerade $ua,(u\in {\Gamma }^{\ast },a\in \Gamma )$ und unter dem Kopf $b\in \Gamma$, ferner rechts davon dann $v\in {\Gamma }^{\ast }$ und auf dem Druckband steht $x\in {\Sigma }^{\ast }$”

• Zu Beginn ist $E$ in der Konfiguration von $(q_{0}w)(\epsilon )$
• falls dann $\delta (q_i,a)=(q_j,b,R,s)$ dann geht $E$ folgend über: $(u{q}_{i}acv)(x)\to (ub{q}_{j}cv)(xs)$
• falls $E$ nach $q_{print}$ übergeht, dann druckt E –> damit wird das Druckband geleert
• falls E nach $q_{stop}$ übergeht, dann stoppt es.

Damit haben wir jetzt einen Enumerator gebaut, der einfach alle möglichen Wörter ausdrucken kann.

[!Tip]

Wie kann mit einem Enumerator eine Sprache beschrieben werden? #card

Die Sprache $L\subseteq {\Sigma }^{\ast }$ eines Enumerators ist die Menge alle Strings, die er ausdruck (was gleichzeitig gleichbedeutend damit ist, dass er sie erkennt!)

Enumerator können auch Sprachen erkennen! (mehr aber nicht zwingend)

[!Satz]

Eine Sprache $L$ ist Turing erkennbar (semi-entscheidbar) genau dann, wenn es einen Enumerator gibt, der sie aufzählt!

Wie können wir das zeigen, was lässt sich dann im Bezug zu “rekursiv-aufzählbar” sagen? #card

Sei $E$ ein Enumerator, der eine Sprache $A$ aufzählt. Wir bemerken, dass $E$ hierbei eine eingeschränkte Form einer Zweiband-TM ist, die auf dem zweiten Band nie liest.

Daraus können wir jetzt die TM $M$ folgend bauen:

1. Auf Eingabe $w$ simuliere $E$ ( eine 2-Band TM). Jedes Mal, wenn $E$ druckt, vergleichen wir die Ausgabe $e_i$ mit $w$
2. Falls dann $e_i=w$ ist, dann akzeptieren –> Wir simulieren sie also, indem wir die Eingabe Schritt für Schritt durchlaufen und jedes mal schauen, ob sie gleich der Eingabe ist –> wenn ja, dann akzeptieren wir und beenden (damit haben wir also erkannt!)

Offensichtlich akzeptiert $M$ genau die Strings, die vom Enumerator $E$ aufgezählt werden (können).

Beweis $⟹$: Sei $M$ eine TM, die eine Sprache $A$ erkennt. Sei $s_1,s_2,\dots$ eine Liste aller Wörter $\in {\Sigma }^{\ast }$ -> wir können die abzählen, weil $\Sigma$ abzählbar ist.

Dann bauen wir jetzt einen Enumerator, der entsprechend diese Liste darstellt und angibt, ob etwas in der Ursprungsprache ist oder nicht.

1. Ignorie den Input
2. Wiederhole für all $i=1,2,\cdots \in \mathbb{N}$ (wir simuliern nur eine begrenzte Menge “mal” eine Eingabe, damit uns nicht mit loopenden Worten verhängen)
3. Simuliere $M$ für $i$ Schritte auf allen Wörtern $s_1,\dots ,s_j$ -> das können wir machen, weil wir eine TM haben) (Weiterhin brauchen wir die Beschränkung auf $i$ Schritte, damit unsere Turing-Maschine nicht endlos läuft und somit das “Halteproblem” verursacht!)
4. Jedes Mal, wenn $M$ ein $s_j$ akzeptiert, dann druckt es der Enumerator! (Damit listen wir alle validen Worte auf, weil wir ja $M$ simulieren!)

Falls jetzt $w\in L(M)$, dann akzeptiert $M$ das Wort $w$ und w wird dann unendlich oft von $E$ gedruckt

Bei dem konstruierten Enumerator ist die Reihenfolge des Ausdruckens der Werte egal, weil in der Simulation irgendwann jedes Wort beliebig oft ausgedruckt wird –> Es folgt aus der Konstruktion der Turing-Maschine.

Die Konstruktion des Enumerators ist nur zum Erkennen von Sprachen gedacht, wenn wir etwa nie ein valides Ende erhalten, wird die konstruierte TM dann einfach für immer warten –> und nicht akzeptieren, weil sie kein valides Wort $w$ erhalten hat.

Wir sehen bei Wörtern, die noch nicht akzeptiert wurden - von dem Enumerator - ein Output von 0 ( die Wörter, die akzeptiert werden werden mit 1 notiert ) gesetzt wird ( aaber das können wir noch nicht ganz evaluieren –> Denn es kann sein, dass die Eingabe einfach zu kurz simuliert wurde ( wir machen ja nur $i$ Schritte der originalen TM durch!))

Daraus sehen wir schon, dass hier manchmal Dinge auftreten, die womöglich niemals berechnet werden können, einfach weil wir sie bis ins unendliche versuchen auszuführen.

Berechenbarkeit

Gibt uns jetzt eine genauere Definition über das obige Problem, was auftreten kann!

[!Definition] Berechenbarkeit

Wann bezeichnen wir eine Funktion $f$ (Turing-) berechenbar (oder auch totalrekursiv)? #card

Eine Fuktion $f:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ heißt Turing-berechenbar oder auch totalrekursiv, falls es eine Turing-Maschine gibt, die bei der Eingabe $w\in {\Sigma }^{\ast }$ den Funktionswert $f(w)$ ausgeben kann

–> Also das Wort wurde auf das Band geschrieben ( war also umsetzbar!) und danach hat sie gestoppt –> $f(w)\in \Gamma$

Bemerkung Die obige Definition enthält eine implizite Beschränkung auf abzählbare Werte. Aus der Mathematik gibt es Funktionen, die auf kontinuierliche Mengen operieren (überabzählbare) –> Diese sind im Allgemeinen nicht Turing-berechenbar

Durch diese Definition können wir jetzt ferner schauen, wann eine Sprache entscheidbar - nicht nur erkennbar! - ist oder nicht.

Charakteristische Funktion | Entscheidbarkeit festlegen

[!Definition]

Eine Sprache $L\subset {\Sigma }^{\ast }$ ist entscheidbar, genau dann wenn ihre charakteristische Funktion folgend gegeben ist: $$1_L:{\Sigma }^{\ast }\to \{0,1\},1_L(w)=\{\begin{array}{ll}>1& \text{ wenn }w\in L\\ >0& \text{ sosnt}>\end{array}$$

Was sagt uns die Konstruktion dieser charakteristischen Funktion? Wie beweisen wir das womöglich? #card

Sie geht quasi alle Werte aus der Hülle - also allen Wörtern, die mit dem Alphabet generiert werden können - durch und prüft, ob über eine Simulation einer TM ( die die Sprache darstellt) das Wort akzeptiert wird / oder nicht.

Beweis dafür:

1. L entscheidbar $⟹1_L$ berechenbar Wir haben eine TM $M$, die $w$ genau dann akzeptiert, wen $w\in L$. Wir erweitern die TM jetzt zu $\overline{M}:$ Falls jetzt $M$ akzeptiert, schreibe wir anschließend eine $1$ auf das Band und löschen alle anderen Werte. (danach stoppen wir)

Falls $M$ verwirft, schreiben wir eine 0 aufs Band und löschen alles andere –> danach stoppen wir auch

2. $1_L$ ist berechenbar $⟹$ L ist entscheidbar Wir haben die TM $\overline{M}$ die $1_L$ berechnet. Wir erwietern sie jetzt zu folgender TM: $M$ Falls $1_L=1$ akzeptiere, Falls $1_L=0$ verwerfe (das wird dann über jeden Inhalt gemacht und somit entschieden, ob das Wort enthalten ist oder nicht!)

Da wir wissen, dass diese Enumerator bzw. charakteristische Funktion entscheidbar ist, können wir dann also bestimmen welche Wörter enthalten sind und welche nicht. Damit wissen wir, dass man irgendwie herausfinden kann, ob das Wort enthalten ist oder nicht –> es muss eine Regel geben und die können wir mit einer TM darstellen!

[!Attention] der Attribut entscheidbar gibt an, dass die $TM$ garantiert terminiert

Berechenbarkeit als Entscheidbarkeit

[!Definition] Berechenbarkeit als Entscheidbarkeit

Eine Funktion $f:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$ ist berechenbar, genau dann, wenn es eine TM gibt, welche die folgende Sprache entscheidet: $$$L_{f}: { w# g \mid w \in \Sigma^{}, g \in \Gamma^{}, f(w) = g }$$

Warum ist das ausschlaggebend, um das zu bestimmen? Wie können wir das etwa beweisen? #card

Wir wollen das Beweisen:

1. Sei $f$ berechenbar Dann heißt das, dass es eine TM $M_1$ gibt, die bei der Eingabe von $w\in {\Sigma }^{\ast }$ die Ausgabe $f(w)$ berechnet! (Das haben wir zuvor gesehen!) Wir bauen dann jetzt $M_2$. Sie bekommt ein Wort der Form $w\#g$ als Eingabe und ruft dann $M_1$ auf die Eingabe $w$ auf (berechnet sie anschließend). -> Wir wissen, dass $M_1$ terminieren wird, weil $f$ berechenbar ist! Dann wartet $M_2$ einfach auf das Ergebnis $g_1$ von $M_1$ und vergleicht es dann mit der Eingabe $g$

–> Wenn die Werte gleich sind (wie erwartet), dann akzeptieren wir! sonst verwerfen wir.

2. Sei $M_2$ eine TM, welche $L_f$ entscheidet. Wir konstruieren $M_1$ welche dann $f$ berechnet:

• Eingabe für $M_1$ ist Wort $w$
• Nun probiert $M_2$ nacheinander alle $w\in {\Gamma }^{\ast }$(Alle Wörter die aus dem Band-Alphabet erzeugt werden können!)
• Also folgend: $w\3 \varepsilon \in L_{f}, w#0 \in L_{f}, w#1 \in L_{f}, w#10 \in L_{f}, w#11\in L_{f}? \dots$
• Dabei läuft die TM jetzt so lange, bis sie eine richtige Antwort trifft -> das passiert in endlicher Zeit, weil $f$ berechenbar ist und das fordert!.
• Tritt dieser Fall ein, dann geben wir $g=f(w)$ als Antwort zurück!

[!Attention] Trick: ${\Gamma }^{\ast }$ ist abzählbar und Entscheidbarkeit bedeutet, dass $M_2$ immer anhält

( also die, die die Sprache der Funktion entscheidet!)

Motivation für die obige Betrachtung | Äquivalenz

Wir möchten hier bestimmte Äquivalenzen betrachten und sehen, dass die Berechenbarkeit einer Funktion im Kontext von mathematischen Funktionen gleich der Frage der Entscheidbarkeit einer Sprache ist / sein kann.

Bei diophantischen Gleichungen hat man etwa gehofft, dass es einen Algorithmus / oder ein Verfahren gibt, dass entscheiden kann ob eine solche Gleichung lösbar ist.

Warum das nicht geht: -> Wenn sie lösbar ist, dann wird sie etwa nach beliebigem Probieren auch resultiert und wir haben etwa eine TM, die dann akzeptiert. –> Wenn Sie nicht lösbar ist, werden wir es dennoch probieren und schauen, ob es für beliebige Werte funktioniert.

[!Tip] Wie lange werden wir diesen Ablauf dann betrachten, bei welchen Eingaben wird nicht mehr probiert? -> Man sieht hierbei, dass man also nicht wirklich beenden wird, weil es ja vielleicht doch noch akzeptieren könnte ( das ist im Kerne das Halteproblem, wir wissen nicht, ob sie jeweils beenden wird oder ob die Antwort noch kommt)

Dafür gibt es also maximal einen Erkenner, aber keinen Berechner!

Gödel zur Berechenbarkeit | Entscheidbarkeit:

[!Satz] Folgerung für Berechenbarkeit

Was können wir über diverse Wörter aussagen, die von einer berechenbaren Funktion bestimmt werden? Was folgt für Turing-Maschinen? #card

1. Die Werte einer berechenbaren Funktionen definieren eine entscheidbare Sprache, und jede entscheidbare Sprache definiert eine berechenbare Funktion

2. Deshalb heißen Sprachen die Turing semi-entscheidbar sind auch rekursiv aufzählbar.

3. Unser Beweis benutzte eine “brute-force” Methode, die funktioniert, weil man berechenbare Sprachen rekursiv “durchtesten” kann.

[!Idea]

Wir werden nun den gleichen Trick auf einer höheren Abstraktionsebene verwenden, um alle Turingmaschinen zu enumerieren. Dieser Prozess ist ein Fall von Gödelisierung (der rekursive Aufzählung einer formalen Sprache).

Das Ergebnis dieses Prozesses ist eine neue Turing-Maschine, die die natürlichen Zahlen $n\in \mathbb{N}$ surjektiv auf den Raum aller Turing-Maschinen abbildet. Eine Programmiersprache für Turing-Maschinen. Die universelle Turing-Maschine.

Codierung einer Turing-Maschine

Statt jetzt die Sprache einer Turing-Maschine rekursiv aufzählen zu können, möchten wir jetzt ferner einfach den Raum aller Turing-Maschinen rekursiv aufzählen.

Dadurch können wir alle Turing-Maschinen so codieren, dass wir später eine Eingabe tätigen und diese Codierung dann die entsprechend benötigte Turing-Maschine ausgibt, die wir brauchen, um das zu berechnen!

Hierbei sehen wir dann, dass es abzählbare unendliche Turing-Maschinen geben wird / kann.

Wir wollen jetzt die Codierung durchführen

[!Definition] Codierung einer Turing-Maschine

Angenommen wir haben eine gegegeben TM $M$ und möchten sie quasi in eine Codierung übersetzen, sodass eine Turing-Maschine dann beim bearbeiten einer Eingabe eventuell auf diese Codierung akzeptiert und das Wort an diese TM weitergibt. Ferner wollen wir sie mit folgendem Alphabet kodieren/darstellen: $\Sigma =\{0,1\}$

wie gehen wir vor, um diese Turing-Maschine zu kodieren? Was folgt hieraus, in Hinsicht auf Berechenbarkeit als Entscheidbarkeit? #card

Idee: Wir müssen jeden Buchstaben und jeden Zustand kodieren.

Für die Buchstaben nutzen wir einfach ein Präfix - damit wir wissen, dass jetzt ein Buchstabe kommt - in der Struktur $10^{j}1$ wobei $j$ der $j$-te Buchstabe ist.

Umsetzung:

1. Sei jetzt das Bandalphabet $\Gamma =\{A_1,\dots ,A_i\}$. Wir codieren jeden Buchstaben - für alle, die auch $\in \Sigma$ sind, nehmen wir die gleiche Kodierung! - mit folgender Struktur: $$code(A_j)=10^{j}1,⟹A_2=1001$$ Und können somit eindeutig kodieren, dass jetzt ein Buchstabe beginnt (mit einer 1 am Anfang und Nullen danach)

2. Sei $Q=\{q_1,\dots ,q_m\}$ die Menge der Zustände. Ferner $q_1=q_0,q_2=q_{accept},q_3=q_{reject}$ (also die Initialzustände). Wir codieren sie folgend: $$code(q_i)=110^{j}11;q_4⟹11000011$$

3. Bewegungen des Schreibkopfes codieren wir folgend: $$code(L)=1110111,code(R)=11100111$$

4. Und die Übergangsfunktion folgend: $$code(\delta (q,a))=(\hat{q},\hat{a},B)=\#code(q)code(a)code(\hat{q})code(\hat{a})code(\hat{B})\#$$ Wobei wir $\#$ folgend entfernen, indem wir es auch codieren.

5. Codiere die ganze TM $M$ mit $\mid Q\mid =m$ Zuständen, und $\mid \Gamma \mid =r$ als: $$code(M)=\#0^m\#0^r\#\#code(Transitio{n}_1)\#code(Transitio{n}_2)\#\dots$$

Da wir jetzt noch $\#$ drin haben, müssen wir alles so codieren, dass wir im binären 4 (bzw. 3) Zeichen eindeutig darstellen können: $$\begin{array}{rl}>0& \to 00\\ >1& \to 11\\ >\#& \to 01>\end{array}$$

[!Attention]

Wir haben soeben eine Funktion - die berechenbar ist! - definiert, die somit, nach der obigen Aussage, also auch eine entscheidbare Sprache darstellt und definiert –> genau die Sprache, die eine Codierung bekommt und schaut, ob es sich um eine valide Codierung handelt oder nicht –> Sie kann aufzählen, welche Strings $\in \{0,1{\}}^{\ast }$ eine Turing-Maschine beschreiben und welche nicht!

[!Attention] Es ist nicht die beste Darstellung bzw. Codierung für die TMs

Dennoch haben wir jetzt eine eindeutige also injektive Abbildung konstruiert!

Eigenschaften der Codierung

Wir können aus der obigen Codierung jetzt einige Grundlegende Ideen und Eigenschaften definieren und beziehen:

[!Req] Folgerungen / Eigenschaften

Unter Betrachtung der oberen Codierung einer Turing-Maschine, was können wir über die erzeugte Abbildung aussagen? Lässt sich eine entscheidbare Sprache bilden, warum? #card

• Wir können aussagen, dass die Codierung injektiv ist, es gilt also: $$code(M_1)=code(M_2)⟹M_1=M_2$$

Jedoch gilt nicht, dass zwei äquivalente TMs zwingend die gleichen Codes haben –> siehe Programmiersprachen und verschiedene Implementierungen einer Funktionalität

• Es gibt eine TM $A_{valid}$, die für einen beliebigen, binären String $w$ entscheiden kann, ob es eine gültige Codierung ist, oder nicht. Somit kann man die folgende Sprache dann als entscheidbar einstufen ( was Sinn ergibt, weil wir ja oben eine berechenbare Funktion definiert haben, und genau diese anwenden können,um dann zu prüfen, ob ein gegebener String eine Codierung ist, oder nicht) $$L=\{w\in \{0,1{\}}^{\ast }\mid w\text{ ist Code fu¨r eine TM}\}$$
• Diese Codierung ist präfix-frei: Kein echtes Präfix einer Codierung von $code(M)$ ist selbst eine Codierung einer anderen $\overline{M}$ TM.
• –> (Das heißt dann, dass bei einer validen Codierung niemals eine andere Codierung inbegriffen und dadurch auftreten kann!
• Das erzeugen wir durch den Anfang, wo wir die Menge von Einträgen,sowie die Übergangsfunktion definieren –> damit haben wir kein allgemeines Präfix

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!

Da wir eine klare Struktur und Definition zur Codierung der Turingmaschine haben, können wir jetzt ganz gut herausfinden, ob eine Codierung eine valide TM ist oder nicht.

[!Important] lineare Ordnung der Menge aller Turing Maschinen

warum haben wir eine lineare/totale Ordnung von Turing-Maschinen erhalten? Was folgt ferner über die Menge von Turing-Maschinen? #card

Da wir jetzt eine Konstruktion gefunden haben, die jede TM in einen binär-String umschreibt, haben wir also eine Abbildung gefunden, die jede Turing-Maschine im Raum der $\mathbb{N}$ abbildet –> es gibt also abzählbar-unendlich viele Turing-Maschinen. <–

Ferner können wir eine lineare Ordnung einführen: Sei $x,y\in \{0,1{\}}^{\ast }$. Wir sagen jetzt, dass $x\le y$, falls die natürlichen Zahlen $n_x,n_y$ die durch die Strings repräsentiert werden, die Eigenschaft haben, dass $n_x\le n_y$ –> dadurch folgt dann: $$\epsilon \le y,\forall y\in \{0,1{\}}^{\ast }$$

Und es ist eine totale Ordnung, weil die Eigenschaften eingehalten werden:

1. $a\le a$ ( Reflexivität)
2. $(a\le b)\wedge (b\le c)⟹(a\le c)$ (Transitivität)
3. $(a\le b)\wedge (b\le a)⟹(a=b)$ (Antisymmetrie)
4. $(a\le b)\vee (b\le a),\forall a,b\in \mathbb{X}$ (total)

Gödelnummern:

Die obige Darstellung bzw. Konvertierung der Turing-Maschinen ist sehr ineffizient –> viele Darstellungen sind keine wirkliche Turing-Maschine und damit haben wir in dem Raum der Turing-Maschinen viele Lücken. Das es aber eine totale Ordnung ist, können wir hier einfach von “links nach rechts” durchnummerieren und jeder dieser Codierungen eine Nummer zuweisen.

Wir wollen sie ferner definieren, da sie nicht nur für diese Abbildung existiert!

[!Definition] Gödelnummern

Sei $x\in \{0,1{\}}^{\ast }$ Für $i\in \mathbb{N}$ nenn wir dann $x$ die Codierung der $i$ten Turingmaschine, wenn folgend zwei Eigenschaften gelten:

1. $x=code(M)$, ist also ein Code für eine Turingmaschine
2. Die Menge $\{y\in \{0,1{\}}^{\ast }\mid y\le x\}$enthält genau $i-1$ Wörter, die Codierungen von Turingmaschinen sind. (Damit stellen wir die richtige Stelle in der Nummerierung sicher)

Wir nennen dann $x$ die Gödelnummer von $M$ und beschreiben diese Gödelnummer für eine TM mit: $$⟨M⟩=x$$ –> Intuitiv ist $⟨M⟩$ das Programm - in Maschinencode - von $M$

[!Important] Nummerierung ist abhängig der Codierung! Denn je nachdem, wie wir die Turing-Maschinen kodieren, ist die Reihenfolge dieser anders / verschieden.

[!Req] $\exists$ Turingmaschine, die für $i$ die Codierung der $i$ten TM berechnet

Was wäre eine Überlegung das umzusetzen und definieren zu können? #card

$A$, was die TM sein wird, könnte die binären Strings in der Ordnung durchlaufen. Auf jeden String $w$ wird dann die TM ( zum berechnen, ob ein String eine valide Codierung ist) $A_{valid}$ angewandt, um zu entscheiden ob $w$ eine TM definiert. Falls ja, dann erhöhen wir den Zähler ($i$).

Wenn sie jetzt bis $i$ gezählt hat - was gefordert war - dann gibt sie diesen String $w$ wieder.

Dadurch ist diese TM $A$ ein Enumerator für Turing-Maschinen!

Gödelisierung

Es gibt viele verschiedene Codierungen von Turing-Maschinen, und dadurch variiert auch die Art der Gödelnummern - bzw welche TMs sie jeweils kodieren!.

[!Definition]

Sei $\mathcal{M}$ die Menge aller Turing-Maschinen. Die Abbildung $g:\mathcal{M}\to \mathbb{N}$ heißt Gödelisierung von $\mathcal{M}$, falls drei Eigenschaften erfüllt werden.

welche drei sind das? #card

1. $g$ ist injektiv, also $((g(M_1))=g(M_2))⟹(M_1=M_2)$
2. Die Bildmenge $g(\mathcal{M})$ ist entscheidbar, also es gibt eine TM, die für jedes $n\in \mathbb{N}$ entscheided, ob $n\in g(\mathcal{M})$ oder nicht
3. Die Funktionen $g:\mathcal{M}\to \mathbb{N}$ und $g^{-1}:g(\mathcal{M}\to \mathcal{M})$ sind berechenbar (weil wir sonst ja nicht abbilden und eine Sprache damit beschreiben können, siehe Berechenbarkeit als Entscheidbarkeit)

Dann gilt für $M\in \mathcal{M},g(M)$ beschreibt die Gödelnummer dieser TM!

Damit ist die Menge aller Turingmaschinen rekursiv aufzählbar –> was auch heißt, dass sie abzählbar unendlich sind!

Wir können dann jetzt wohl auch eine Turing-Maschine beschreiben, die sie erkennen kann!

Universelle Turing Maschinen

112.14_universal_turing_machine