Das Halteproblem - Versionsgeschichte

Css am 14. August 2018 um 21:15 Uhr

2018-08-14T21:15:05Z

Css am 14. August 2018 um 21:12 Uhr

2018-08-14T21:12:31Z

Css am 14. August 2018 um 17:59 Uhr

2018-08-14T17:59:44Z

Css am 14. August 2018 um 17:56 Uhr

2018-08-14T17:56:31Z

Css: Die Seite wurde neu angelegt: „Wie schon bei der universellen Registermaschine gesehen, kann man Programme schreiben, die wiederum Dinge mit anderen Programmen machen, zum Beispiel sie auszu…“

2018-08-14T17:47:13Z

Die Seite wurde neu angelegt: „Wie schon bei der universellen Registermaschine gesehen, kann man Programme schreiben, die wiederum Dinge mit anderen Programmen machen, zum Beispiel sie auszu…“

Neue Seite

Wie schon bei der universellen Registermaschine gesehen, kann man Programme schreiben, die wiederum Dinge mit anderen Programmen machen, zum Beispiel sie auszuführen. Man könnte sie aber auch anderweitig analysieren.

Nun ist ein wichtiges Problem bei solchen Maschinen, ob sie jemals halten werden, also jemals eine <code>End</code>-Anweisung erreichen. Alan Turing stellte sich die Frage, ob man dies im Allgemeinen lösen könnte. Das Problem nennt sich '''Halteproblem'''.

Formaler ist die Frage, ob es ein Programm $M$ mit Eingaben $R_1$ und $R_2$ gibt, sodass in $R_1$ ein codierter Programmcode steht (wie vorhin bei der universellen Registermaschine), und in $R_2$ eine codierte Folge von Registern als Eingabe (ebenfalls analog zur universellen Registermaschine), sodass $M$ genau dann $R_3$ auf $0$ gesetzt lässt, wenn dieses Programm mit den gegebenen Eingaben terminiert.

Nehmen wir an, ein solches Programm $M$ würde existieren. Wir können daraus ein Programm $N$ generieren, das folgendes tut:

"führe M aus"
if R[3] == 0 then goto Loop
End
Loop: goto Loop

Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert.

← Nächstältere Version		Version vom 14. August 2018, 21:15 Uhr
Zeile 22:		Zeile 22:
	$O$ terminiert genau dann, wenn das in $R_1$ codierte Programm mit sich selbst als Eingabe terminiert. Man nennt solche Programme '''self-accepting'''. Sei nun $O$ codiert durch $o$. Dann können wir $O(o)$ berechnen, also $O$ mit $R_1=o$. Die Frage ist nun, ob $O(o)$ terminiert.		$O$ terminiert genau dann, wenn das in $R_1$ codierte Programm mit sich selbst als Eingabe terminiert. Man nennt solche Programme '''self-accepting'''. Sei nun $O$ codiert durch $o$. Dann können wir $O(o)$ berechnen, also $O$ mit $R_1=o$. Die Frage ist nun, ob $O(o)$ terminiert.

−	~~[[Kategorie:TODO]]~~	+	Angenommen, $O(o)$ terminiert. Das bedeutet, dass in $O$ nach der Ausführung von $M$ gilt $R_3=0$. Also würde $O(o)$ nicht terminieren. Widerspruch.
		+
		+	Angenommen, $O(o)$ terminiert nicht. Das bedeutet, dass in $O$ nach der Ausführung von $M$ gilt $R_3\neq 0$. Also würde $O(o)$ terminieren. Widerspruch.
		+
		+	Beide möglichen Fälle sind widersprüchlich. Das bedeutet, dass es ein solches Programm $M$ nicht geben kann. Das Halteproblem ist nicht lösbar.

@@ Zeile 12: / Zeile 12: @@
      Loop: goto Loop
-Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert.
+Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert. Nun modifizieren wir das Programm erneut, und erhalten das Programm $O$:
-Sei nun $N$ codiert durch die Zahl $n$.
+    "setze R[2] auf <R[1]>"
 [[Kategorie:TODO]]

← Nächstältere Version		Version vom 14. August 2018, 17:59 Uhr
Zeile 15:		Zeile 15:

	Sei nun $N$ codiert durch die Zahl $n$.		Sei nun $N$ codiert durch die Zahl $n$.
		+
		+	[[Kategorie:TODO]]

← Nächstältere Version		Version vom 14. August 2018, 17:56 Uhr
Zeile 13:		Zeile 13:

	Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert.		Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert.
		+
		+	Sei nun $N$ codiert durch die Zahl $n$.