Halteproblem und Church-Turing-These

[Mark22]

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.

[MartinSt]

Hallo

in Halteproblem ? Wikipedia wird genau dieser Pseudocode erläutert, inkl. der dahinterstehenden math. Theorie.

Gruß Martin

[flashpixx]

Dein Prof hat das Beispiel aus Wikipedia verwendet Halteproblem ? Wikipedia

Ein kleiner Ratschlag: Es geht bei der Analyse von solchen Problemen nicht um den Quellcode, sondern um Logik. Ich würde Dir empfehlen das als Prädikaten Ausdruck zu schreiben, das ist dann unabhängig von dem Quellcode.

Zur Church-Turing-These: Dir ist sicher bekannt, dass diese nicht formal beweisbar ist. Das "intuitiv" bedeutet, dass man einen (sinnvollen) Berechnungsformalismus finden kann. Die These gilt z.B. für TM, While-Programme, Goto-Programme, Lambda-Kalkühl, Mü-Rekursive-Funktionen...

Zum Halteproblem: Bei dieser Fragestellung geht es darum zu zeigen, dass ein Algorithmus für jede Eingabe von Daten, terminiert und damit ein definiertes Ergebnis liefert. D.h. wenn sich der Algorithmus in einer "Endlosschleife" aufhängt, d.h. er hält nicht, dann ist das Halteproblem nicht gelöst. Gedanklich gibt man in Deinem Fall einer TM eine TM mit Daten und möchte nun wissen, ob diese eingegebene TM terminiert oder nicht.

Man macht leicht den Fehler, dass man sich bei der Betrachtung an dem konkreten Beispiel fest hält, es geht hier aber um einen Formalismus, d.h. es muss für jede Art Eingabe gelten

Phil