Siehe auch

Schlagwörter

• Entscheidbarkeit
• Programmiermaschine
• Logik-Programmierung
• reflexiv-transitive Hülle
• Graphentheorie
• Fixpunktsemantik
• Künstliche Intelligenz (KI)

Literatur

• Alexander Asteroth, Christel Baier: Theoretische informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale sprachen, Pearson, München 2003, ISBN 3-8273-7033-7
• Katrin Erk, Lutz Priese: Theoretische informatik. Eine umfassende Einführung, Springer, Berlin 2002, ISBN 3-540-42624-8
• Bernhard Heinemann, Klaus Weihrauch: Logik für informatiker. Eine Einführung, Teubner, stuttgart 2000, ISBN 3-519-12248-0
• John E. Hopcroft u.a.: Einführung in die Automatentheorie, formale sprachen und Komplexitätstheorie, Pearson, München 2003, ISBN 3-8273-7020-5
• John Kelly: Logik im Klartext, Pearson, München2003, ISBN 3-8273-7070-1
• Uwe Schöning: Theoretische informatik - kurzgefasst, Spectrum Akadem. Verlag, Heidelberg 2003, ISBN 3-8274-1099-1
• Ingo Wegener: Theoretische informatik. Eine algorithmische Einführung, Teubner, stuttgart 1999, ISBN 3-519-12123-9
• Klaus Weihrauch: Computability, Springer, Berlin 1987, ISBN 3-540-13721-1
• Renate Winter: Theoretische informatik. Grundlagen mit Übungsaufgaben und Lösungen, Oldenbourg, München 2002, ISBN 3-486-25808-7

Berechenbarkeitstheorie

Insbesondere geht es um die Analyse der internen Struktur von Problemen und um die Klassifikation von Problemen nach verschiedenen Graden der Unlösbarkeit.In der Berechenbarkeitstheorie wird die algorithmische Lösbarkeit von Problemen untersucht.

Dabei ist das Problem des Haltens eine Voraussetzung für das Problem der Verifikation.Ein Ergebnis der Berechenbarkeitstheorie ist die Erkenntnis, dass das Halteproblem unentscheidbar ist, man also keinen Algorithmus Finden kann, der ein beliebiges Programm daraufhin untersucht, ob es jemals (bei einer bestimmten Eingabe) anhält oder in einer Endlosschleife weiterläuft. Ebenfalls unentscheidbar ist das dem Halteproblem innenliegende Verifikationsproblem, bei dem ein beliebiges Programm überprüft werden soll, ob es eine bestimmte mathematische Spezifikation erfüllt. Aus der Unentscheidbarkeit folgt, dass diese beiden Fragestellungen nicht für alle Algorithmen entschieden werden können. Im speziellen kann dies jedoch für bestimmte Algorithmen möglich sein.