Halteproblem- Entscheidbarkeit < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Ich verstehe das halteproblem nicht! |
Betrachten Sie bitte folgenden beweis:
[Dateianhang nicht öffentlich]
folgendes verstehe ich (mal rückwaerts aufgedroeselt):
w [mm] \not\in [/mm] K [mm] \gdw [/mm] f'(w)=1
nur wie komme ich dann auf die absurde annahme dass
daraus folg:
[mm] \gdw M'=M_w [/mm] angesetzt auf w hält [mm] \gdw [/mm] w [mm] \in [/mm] K
???
ich glaube ich bringe da irgend etwas mit der entscheidbarkeit durcheinander, waere echt super wenn mir jemand zum neuen jahr der das halteproblem immanent verstanden hat was dazu erlaeutern koente
gruss
christian
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
| |
|
Hallo christian,
so schwer es einem auch fallen mag, dies am Anfang zu begreifen: Jede Aequivalenz
folgt direkt aus einer Definition oder Annahme, ist also elementar.
Gehen wir es durch:
[mm] \omega' \not\in [/mm] K [mm] \Leftrightarrow [/mm] (nach definition der partiellen Funktion f')
[mm] f'(\omega') [/mm] =1 [mm] \Leftrightarrow [/mm] (nach Def. der Funktion f')
[mm] M'=M_{\omega'} [/mm] (das ist ja die Annahme, dass es solches [mm] M'=M_{\omega'} [/mm] fuer f' gibt)
haelt auf Eingabe [mm] \omega' [/mm] und gibt 1 aus
[mm] \leftrightarrow (nach definition des halteproblems) \omega'\in K -Widerspruch.
Also kann eben nicht die Funktion f' partiell rekursiv sein und somit auch nicht
das Halteproblem entscheidbar.
Wie man sieht: Auch und gerade Beweise, in denen jeder Schritt elementar ist, koennen
es in sich haben.
Ein besseres Beispiel hierfuer ist uebrigens der Rekursionssatz, zur Lektuere
des selbigen kann man auf das textbuch von Rogers zurueckgreifen.
Allen einen guten Start ins neue Jahr !
Mathias
[/mm]
|
|
|
|
