Hallo,
habe bald eine mündliche Prüfung in Informatik und habe deswegen ein paar Fragen. Wäre nett, wenn jemand helfen könnte.
haltetest(Programm, Eingabe)
1 wenn Programm(Eingabe) terminiert
2 dann return Ja
3 sonst return Nein
test(Programm)
1 solange haltetest(Programm, Programm) == Ja
2 führe aus keine Aktion
test(test); // Dieser Aufruf terminiert genau dann,
// wenn er nicht terminiert. (Widerspruch!)
Diesen Pseudocode hat unserer Professor auch benutzt. Ich verstehe folgendes daraus: Wenn unser Programm A haltetest durch eine Eingabe terminiert, dann wird als Return ja ausgegeben.
Das zweite Programm B test prüft immer ob Programm A terminiert. Sollte das der Fall sein, führt dieses keine Aktion mehr aus.
Das Problem jetzt, soweit ich es verstehe, das Programm B nicht terminiert wenn Programm A terminiert. Da ist ein Widerspruch?!
Nun in Verbindung mit der Chursche These. Da komm ich auch net genau weiter. Ich kann so viel sagen, dass die Turingmaschinen nicht in der Lage sind solche Probleme wie das Halteproblem zu lösen. Aber schlau werde ich daraus kein bisschen.
Vielen Dank im vorab für eure Hilfe.
