date-created: 2024-02-21 12:07:36 date-modified: 2024-06-12 08:22:17

Gödelnummer / universelle Turing-maschinen :

part of [[112.00_anchor_overview]]

Motivation

Wir haben zuvor gezeigt, dass man TMs codieren kann, und dass das entscheidbar ist!,

Ferner muss es also auch möglich sein eine Turing-Maschine zu konstruieren, die eine solche Codierung erkennen und anschließend simulieren kann.

Vergleichen wir das etwa nochmal mit realistischen Modellen: Wir haben jetzt immer TMs betrachtet, die ein spezifisches Programm durchlaufen / bearbeiten können. Aber wir haben keine programmierbare Struktur - TM - erschaffen, wie man es aus der Realität kennt. Das möchten wir mit der Universellen Turing-Maschine jetzt beheben und somit auch einführen!

[!Idea] Idee der universellen Turingmaschine $U$

Wir konstruieren jetzt die universelle Turingmaschine $U$, welche eine Gödelnummer erhält und diese entsprechende Turing-Maschine simuliert. Genauer heißt das:

Wie funktioniert diese Turingmaschine? #card

• Als Eingabe erhält $U$ die Gödelnummer $⟨M⟩$ und ein beliebiges Wort $w$, auf das die TM $M$ (die wir codierten) ausgeführt werden soll
• $U$ soll nun die Operationen von $M$ auf $w$ simulieren, also auf $w$ anwenden.
  • sie soll akzeptieren, wenn $M$ das wort $w$ akzeptiert( en würde)
  • sie soll die Ausgabe $x$, die von $M$ erzeugt werden würde, ebenfalls aufs Band schreiben
• Bei inkorrekter Eingabe - etwa kein gültiger Code o.ä. - wird $U$ einen Fehler ausgeben!

Definition

[!Definition] Konstruktion der universellen Turing-Maschine

Wir wollen jetzt die universelle TM konstruieren und brauchen hierfür 3 Bänder.

1. Band 1 simuliert das Band von $M$ - o.B.d.A. gehen wir davon aus, dass sie nur eins hat ( sonst umwandeln)
2. Band 2 speichert die Gödelnummer -> also den Programmcode der TM!
3. Band 3 speichert den aktuellen Zustand von $M$

Wie funktioniert diese Maschine jetzt? #card

1. Zu Beginn $q_0^U$ steht die Eingabe $⟨M⟩,w$ auf Band 1 -> beide anderen sind leer
2. $U$ liest jetzt die Eingabe und teilt sie in die Gödelnummer und w -> da wir passend kodieren können, geht das!
3. $U$ verfährt, wie $A_{valid}$ um zu entscheiden, ob die Gödelnummer eine valide Codierung ist. Wenn nicht, bricht sie ab
4. Nun kopiert $U$ die Gödelnummer $⟨M⟩$ auf Band 2, löscht sie also von Band1. (damit haben wir die Simulation von $M$ initialisiert) Auf Band 3 schreiben wir die Codierung des Startzustandes $q_0^M$ der simulierten TM $M$

Jetzt muss ein Rechenschritt simuliert werden!

1. $U$ kennt $q^M$ auf Band 3
2. $U$ liest den aktuellen Buchstaben der Eingabe $w$
3. $U$ liest aus Band 2 den zugehörigen Übergang ${\delta }^M(q^M,w_i={\overline{q}}^M,\overline{w},B$
4. $U$ führt diesen Übergang auf Band 1 aus und schreibt den neuen Zustand auf Band 3!

$U$ stoppt jetzt, sobald auf Band 3 der akzeptierende/verwerfende Zustand erreicht wurde. Auf Band1 steht dann die Ausgabe der Berechnung

Universal TM, als partiell entscheidbare Funktion

[!Bsp]

Da $A_{valid}$ entscheidet ( was wir nutzen, um herauszufinden, ob die Codierung valide ist), definiert $U$ eine partiell berechenbare Funktion $$U(⟨M⟩,\circ )=M(\circ )$$

warum ist sie partiell berechenbar? #card

Die universelle TM kann eine Codierung in endlicher Zeit realisieren / entscheiden Charakteristische Funktion Entscheidbarkeit festlegen und führt dann anschließend die Eingabe auf der Simulation aus: (bei dieser Codierung verwirft oder akzeptiert sie also garantiert)

Wenn sie beliebige Eingabe tätigt, dann kann sie hier wieder halten/verwerfen/akzeptieren, jenachdem, was für eine Turingmaschine man betrachtet etc.

(alternative) Konstruktion Universeller TM :

Aus der Vorlesung und Betrachtung von Ulrike Luxburg

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_Mengen]]

Fun-Fact: Die kleinste universelle Turingmaschine

Wurde von Yurii Rogozhin entwickelt / “gefunden”. (weiterer link)

[!Idea] Motivation

Wir haben oben eine UTM als 3-Band Turingmaschine beschrieben und definiert

• Band 1 simulierte Band von M, Band 2 speicherte die Gödelnummer, Band 3 den Zustand von M

Wir wissen aber, dass Mehrband = Einband und somit kommt die Frage nach der kleinsten universellen Turingmaschine auf!

Das hat sich auch Yurii Rogozhin gedacht und diverse kleine Turing-Maschinen konzipiert:

• UTM(24,2), UTM(10,3), UTM(7,4), UTM(5,5), UTM(4,6),
• UTM(3,10), UTM(2,18).

Ferner ist bekannt: Es ist bekannt dass UTM(3,2),UTM(2,3) und UTM(2,2)!

(Also good read link)

from here https://onthesamepage.berkeley.edu/fall-2013/

Umsetzung kleiner UTMs

Man verwendet hierfür ein Tag-System:

[!Definition] $m$-Tag-System

Ein $m$-Tag-System $T=(m,\Sigma ,P)$ ist ein Tupel aus $m\in \mathbb{N}$, einem Alphabet $\Sigma =\{a_1,\dots ,a_{n+1}\}$ (wobei $a_{n+1}$ das Haltesymbol ist) und einer Produktionsfunktion $P:\Sigma \to {\Sigma }^{\ast }$ mit folgender Struktur: $$P:\{\begin{array}{l}>a_j\to {\alpha }_i\in {\Sigma }^{\ast },\forall i\in \{1,\dots ,n\}\\ >a_{n+1}\to Stop>\end{array}$$

Eine Berechnung von T auf dem Wort $w_9\in {\Sigma }^{\ast }$ ist dann eine Folge $w_0,w_1,\dots ,\in {\Sigma }^{\ast }$, sodass für alle $k,w_k$ in $w_{k+1}$ übergeht, sodass die ersten $m$ Zeichen aus $w_k$ gelöscht und das Wort ${\alpha }_i$ am Ende von $w_k$ angehangen werden kann.

Das geht nur, falls das erste Zeichen von $w_k$ ein $a_i$ ist! Die Berechnung stoppt am Ende, wenn $\mid w_k\mid <m$ oder das erste Zeichen ein $a_{n+1}$ ist!

[!Satz] Satz von Minsky

Zu jeder TM $M$ existiert ein $2$-Tag System, dass zu $M$ äquivalent ist. Dieses System stoppt nur auf Worten, die mit $a_{n+1}$ beginnen und all seine Produktion sind nicht leer.

Und ferner konnte man dieses Tag-System dann auch für die Gödelisierung anwenden!