Berechenbarkeitstheorie

Quelle: Wikipedia. Seiten: 48. Kapitel: Turingmaschine, Gödelscher Unvollständigkeitssatz, Church-Turing-These, Kolmogorow-Komplexität, Berechenbarkeit, Ackermannfunktion, Lambda-Kalkül, Entscheidbar, Quine, Turing-Vollständigkeit, Gentzenscher Hauptsatz, Formales System, Halteproblem, Primitiv-rekursive Funktion, Turingmaschine Typ 2, Reduktion, Gödelnummer, Postsches Korrespondenzproblem, Fleißiger Biber, ¿-Rekursion, Orakel-Turingmaschine, LOOP-Programm, Wang-Parkettierung, Church-Rosser-Theorem, Satz von Rice, Terminiertheit, Abstrakte Zustandsmaschine, WHILE-Programm, Rekursionssatz, GOTO-Programm, Sudanfunktion, Rekursive Aufzählbarkeit, Church-Kodierung, Registermaschine, Speedup-Theorem, Berechenbare Zahl, Smn-Theorem, Charakteristische Funktion, Semi-entscheidbare Menge, Wortproblem, Äquivalenzproblem, Craig-Interpolation, Wortfunktion, Akzeptieren, Halbe charakteristische Funktion, Kleenesche Normalform, Nummerierung, Programmäquivalenz, Notation, Berechenbare Folge. Auszug: Der Gödelsche Unvollständigkeitssatz ist einer der wichtigsten Sätze der modernen Logik. Er beschäftigt sich mit der Ableitbarkeit von Aussagen in Formalen Sprachen. Der Satz zeigt die Grenzen der formalen Systeme ab einer bestimmten Mächtigkeit auf und weist nach, dass es in hinreichend mächtigen Systemen (wie der Arithmetik) Aussagen gibt ¿ und geben muss ¿ die man weder formal beweisen, noch widerlegen kann. Der Satz beweist damit die Unmöglichkeit des Hilbertprogramms, welches von David Hilbert unter anderem gegründet wurde, um die Widerspruchsfreiheit der Mathematik zu beweisen. In der Wissenschaftstheorie und in anderen Gebieten der Philosophie zählt der Satz zu den meistrezipierten der Mathematik. Das Buch Gödel Escher Bach und die Werke von John Randolph Lucas, der versuchte eine Theorie der Menschenrechte mit der Aussage zu zeigen, werden in dem Zusammenhang, zusammen mit ihren ebenso zahlreichen Kritikern, gern exemplarisch herausgehoben. Der Satz wurde zuerst in der Arbeit von Kurt Gödel formuliert und bewiesen: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. in: Monatshefte für Mathematik und Physik 38 (1931), S. 173 ff. Aussagen sind dabei Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen. Für solche Aussagen definiert man auf naheliegende Weise das Konzept der Gültigkeit oder Wahrheit in Strukturen (siehe Modelltheorie). Dabei kann die Wahrheit einer Aussage durchaus von der betrachteten Struktur abhängen: Eine Aussage mit der intendierten Bedeutung ¿Es gibt ein Element, das echt größer als 0 und echt kleiner als 1 ist¿ gilt zum Beispiel in der Struktur der reellen Zahlen, nicht jedoch in der Struktur der natürlichen Zahlen. Der Begriff der Gültigkeit einer Aussage in einer Struktur führt auf natürliche Weise auf einen logischen Folgerungsbegriff, den sogenannten semantischen Folgerungsbegriff: Aussage A folgt aus einer Menge von Aussagen T (einer sogenan