Hallo www-ler,
such im Moment einfach zu verstehende Informationen, die das Halteproblem erklären. Wir nehmen im Moment in der Schule die Turing-Maschine durch und das Halteproblem ist ein Thema davon. Ein alter Thread existiert zwar bereits, aber die Links in den Antworten werden nicht mehr gefunden …
gruß
uladida
such im Moment einfach zu verstehende Informationen, die das
Halteproblem erklären. Wir nehmen im Moment in der Schule die
Turing-Maschine durch und das Halteproblem ist ein Thema
davon. Ein alter Thread existiert zwar bereits, aber die Links
in den Antworten werden nicht mehr gefunden …
Was gefällt Dir an dem Wikiartikel nicht?
http://de.wikipedia.org/wiki/Halteproblem
Das Halteproblem an sich habe ich jetzt verstanden, jedoch weiss ich noch nicht genau warum das problem semi-entscheidbar ist…
gruß
Hi,
Das Halteproblem an sich habe ich jetzt verstanden, jedoch
weiss ich noch nicht genau warum das problem semi-entscheidbar
ist…
Hm. Dann hast Du es nicht an sich verstanden … 
Wo hakt’s denn? Versuch mal, folgende Fragen zu beantworten:
(1) Wie lautet die Fragestellung des „Halteproblems“?
(2) Wie lautet die Definition von „entscheidbar“?
(3) Wie lautet die Definition von „semi-entscheidbar“?
(4) Wie wird der Widerspruch aus der Annahme konstruiert, das Halteproblem sei entscheidbar?
(5) Warum also ist das Halteproblem semi-entscheidbar?
Du bist dran.
Gruß,
Ralf
Ok, ich versuchs mal 
(1) Wie lautet die Fragestellung des „Halteproblems“?
Kann ein Programm entscheiden ob ein zweites Programm + dazugehörige Eingabe terminiert oder nicht terminiert?
(2) Wie lautet die Definition von „entscheidbar“?
ein klares nein und ein klares ja gegeben werden kann
(3) Wie lautet die Definition von „semi-entscheidbar“?
das entweder ein klares nein oder ein klares ja gegeben werden kann
(4) Wie wird der Widerspruch aus der Annahme konstruiert, das
Halteproblem sei entscheidbar?
hmm, hier tu ich mich schon schwer… meinst du das beispiel, wo genau diese Annahme widerlegt wird, also wo das eine programm sich selbst auf terminierung überprüft?
(5) Warum also ist das Halteproblem semi-entscheidbar?
hier weiss ich es eben nicht, aber ich hab eben was gelesen, dass es einfach ein programm geben muss, was das zu prüfende programm simulieren muss. dann sieht man ja, ob es irgendwann abbricht, wenn dies passiert ist es terminiert, wenn nicht dann nicht.
ist das in etwa richtig?
viele grüße
uladida
Ok, ich versuchs mal
Prima!
(1) Wie lautet die Fragestellung des „Halteproblems“?
Kann ein Programm entscheiden ob ein zweites Programm +
dazugehörige Eingabe terminiert oder nicht terminiert?
Genau. Die ‚dazugehörige Eingabe‘ ist eine Zeichenfolge (ein Text). Ein Programm ist auch eine Zeichenfolge (die bestimmten syntaktischen Regeln gehorchen muss). Ich kann also auch ein Programm (eine Zeichenfolge, die ein Programm darstellt) als Eingabe für ein anderes Programm verwenden. Basic-Interpreter machen sowas zum Beispiel.
(2) Wie lautet die Definition von „entscheidbar“?
ein klares nein und ein klares ja gegeben werden kann
Hier passt die Definition „es existiert ein Algorithmus (ein Programm), der sowohl im Ja- als auch im Nein-Fall immer die richtige Antwort liefert.“
(3) Wie lautet die Definition von „semi-entscheidbar“?
das entweder ein klares nein oder ein klares ja gegeben werden
kann
Nicht ganz. „Es existiert ein Algorithmus, der im Ja-Fall immer die richtige Antwort, also Ja, ausgibt. Im Nein-Fall terminiert der Algorithmus nicht.“
Zum Beispiel ist die Frage „Wird Schalke jemals Bundesliga-Meister?“ semi-entscheidbar. Der Algorithmus wertet die Bundesliga-Ergebnisse aus. Wenn Schalke am Ende einer Saison Erster ist, lautet die Antwort „Ja“. Ansonsten wird die nächste Saison abgewartet. So kann es nie ein „Nein“ als Antwort geben, denn vielleicht klappt’s ja nächstes Mal. (Übungsaufgabe: zeige, dass die Frage nicht entscheidbar ist
(4) Wie wird der Widerspruch aus der Annahme konstruiert, das
Halteproblem sei entscheidbar?hmm, hier tu ich mich schon schwer… meinst du das beispiel,
wo genau diese Annahme widerlegt wird, also wo das eine
programm sich selbst auf terminierung überprüft?
Genau.
Angenommen, es gibt ein Programm
EntscheideHP(Programmtext, Eingabetext)
mit der Ausgabe „hält an“ oder „hält nicht an“.
Dann kann ich folgendes Programm schreiben:
RalfsProgramm (Text)
<u>begin</u>
<u>while</u> EntscheideHP(Text,Text) = "hält an" <u>do</u>
<u>print</u> "ich rechne noch"
<u>wend</u>
<u>print</u> "fertig"
<u>end</u>
Wenn „Text“ kein gültiges Programm darstellt, kommt irgendein Murks raus, sonst wird ermittelt, ob das Programm „Text“ mit sich selbst als Eingabe terminiert oder nicht. Wenn Text(Text) anhält, dann gerät RalfsProgramm(Text) in eine Endlosschleife und hält nicht an. Wenn Text(Text) in eine Endlosschleife gerät, hält RalfsProgramm(Text) an.
So, und nun rechne ich aus:
RalfsProgramm(RalfsProgramm)
Was passiert, weißt Du oder kannst es Dir überlegen.
*TILT*
Das einzige schwache Glied in der Kette ist die Annahme, dass das Programm „EntscheideHP(Programm,Eingabe)“ existiert. Die Folgerungen daraus sind Wasserdicht. Also muss die Annahme falsch gewesen sein, es kann kein Programm existieren, das das Halteproblem entscheidet.
Das Halteproblem ist nicht entscheidbar!
Aber vielleicht semi-entscheidbar?
(5) Warum also ist das Halteproblem semi-entscheidbar?
hier weiss ich es eben nicht, aber ich hab eben was gelesen,
dass es einfach ein programm geben muss, was das zu prüfende
programm simulieren muss. dann sieht man ja, ob es irgendwann
abbricht, wenn dies passiert ist es terminiert, wenn nicht
dann nicht.
ist das in etwa richtig?
Ziemlich genau.
(1) Wir wissen: Entscheidbar ist das Halteproblem nicht.
(2) Eine einfache Auswertung des Programms mit dem gegebenen Eingabetext terminiert, wenn das Programm terminiert. Sonst nicht. Das Kriterium für Semi-Entscheidbarkeit ist erfüllt. QED.
Und, jede Klarheit beseitigt?
Viele Grüße,
Ralf
oh super, dann hab ichs ja doch einigermaßen verstanden 
auf jeden fall danke an euch und für die mühen drückt mir die daumen für den vortrag nächste woche
gruß
uladida