Kurt Gödel: Unvollständiglkeitssatz
Hans Magnus Enzensberger
Hommage an GödelMünchhausens Theorem, Pferd, Sumpf und Schopf,
ist bezaubernd, aber vergiss nicht:
Münchhausen war ein Lügner.Gödels Theorem wirkt auf den ersten Blick
Etwas unscheinbar, doch bedenk:
Gödel hat recht."In jedem genügend reichhaltigen System
lassen sich Sätze formulieren,
die innerhalb des Systems
weder beweis- noch widerlegbar sind,
es sei denn das System
wäre selber inkonsistent."Du kannst deine eigene Sprache
in deiner eigenen Sprache beschreiben:
aber nicht ganz.
Du kannst dein eigenes Gehirn
mit deinem eigenen Gehirn erforschen:
aber nicht ganz
Usw.Um sich zu rechtfertigen
muss jedes denkbare System
sich transzendieren,
d.h. zerstoeren."Genügend reichhaltig" oder nicht:
Widerspruchsfreiheit
ist eine Mangelerscheinung
oder ein Widerspruch.(Gewissheit = Inkonsistenz)
Jeder denkbare Reiter,
also auch Münchhausen,
also auch du bist ein Subsystem
eines genügend reichhaltigen Sumpfes.Und ein Subsystem dieses Subsystems
Ist der eigene Schopf,
dieses Hebezeug
fuer Reformisten und Lügner.
In jedem genügend reichhaltigen System
also auch in diesem Sumpf hier,
lassen sich Saetze formulieren,
die innerhalb des Systems
weder beweis- noch widerlegbar sind.Diese Sätze nimm in die Hand
Und zieh!------------------------------------------
Zitiert nach: Hans Magnus Enzensberger.
Die Elixiere der Wissenschaft.
Frankfurt a. M.: Suhrkamp 2002.
Maurits Cornelis Escher
Der Unvollständigkeitssatz von Kurt Gödel lautet (vereinfacht):
Jeder widerspruchsfreie Kalkül (ein geschlossenes formales System), der es erlaubt, von den natürlichen Zahlen zu sprechen, der also die elementare Arithmetik umfasst, enthält unendlich viele Aussagen, die in diesem Kalkül weder bewiesen noch widerlegt werden können.Solche Aussagen heissen unentscheidbar.
Beispiel: Der Kreter Epimenide sagt, dass alle Kreter lügen.
Widerspruchsfreiheit in einem formalen System:
Jeder Satz, wenn er interpretiert wird, führt zu einer wahren Aussage.Wiedersprüchlichkeit:
Unter den interpretierten Sätzen gibt es mindestens eine falsche Aussage. Dabei handelt es sich um einen semantischen Widerspruch, der nur in Bezug zu unseren Erfahrungen geleistet werden kann.
Die systemimmanenten Widersprüche sind formaler (oder syntaktischer) Natur und treten auf, wenn mindestens 2 Sätze sich nicht vertragen. Z.B. kann etwas nicht gleichzeitig rot und nicht-rot sein.Antinomien: echte unaufllösliche Widersprüche (im Gegensatz zur Paradoxie, die nur einen scheinbarer Wiederspruch darstellt)
"Mit der Arbeit des Logikers Kurt Gödel wurden Selbstbezüglichkeiten ins Zentrum der Computertheorie gerückt. Wesentliche Erkenntnisse über die Grenzen der Berechenbarkeit beruhen auf der Tatsache, dass hinreichend komplexe Systeme (lebende Organismen, aber auch Maschinen) zur Selbstreferenz fähig sind. Wenn Systeme Aussagen über sich selbst, ihre Eigenschaften und Verhalten machen, können sie sich in unauflösbare Widersprüche verstricken." Solche Phänomene nennt man Antinomien.
"Die drei Kennzeichen semantischer Antinomien sind:
- Selbstbezogenheit: 'Dieser Satz enthält fünf Wörter.' Ist selbstbezogen, aber weder widersprüchlich noch zirkelhaft.
- Widersprüchlichkeit: 'Dieser Satz enthält sechs Wörter'. Ist selbstbezogen und widersprüchlich, aber nicht zirkelhaft.
- Zirkelhaftigkeit: 'Dieser Satz ist falsch'. Ist selbstbezogen und widersprüchlich, aber auch zirkelhaft."
Trogemann, Viehoff: Code@Art, S. 90/1
Gödels Unvollständigkeitssatz besagt nun Folgendes: dass es in der Zahlentheorie (Arithmetik) Wahrheiten gibt, die nicht bewiesen werden können.
Vollständigkeit:
Lässt sich in einer Sprache der Wahrheitswert grundsätzlich aus ihren Axiomen deduzieren (herleiten), wir diese Sprache vollständig genannt.
Bsp: Schach oder Go. Unvollständigkeit würde bedeuten, dass es Spielstellungen geben kann, die nicht von der Anfangsposition erreicht werden können unter Einhaltung der Spielregeln.Nach Gödel ist jedes logische System, das hinlänglich komplex ist (die Zahlentheorie enthält), entweder unvollständig oder widersprüchlich. Es gibt arithmetische Ausagen, deren Wahrheit oder Falschheit nicht mit Hilfe der Axiome und Rechenregeln bewiesen werden kann. Gödel hat mit der Logik bewiesen, dass es Dinge gibt, die nicht beweisbar sind.
Oder: es gibt mathematische Probleme, die sind berechenbar und andere sind nicht-berechenbar.
Freeman Dyson: "Gödel hat bewisen, dass reine Mathematik unerschöpflich ist; keine endliche Reihe Axiome und Interferenzregeln wird den ganzen Umfang der Mathematik erfassen. Bei jeder beliebigen Menge Axiome lassen sich sinnvolle mathematische Fragestellungen finden, die von diesen Axiomen nicht beantwortet werden. ... Sofern ich die Zukunft richtig einschätze, ist auch die Welt der Physik und die Welt der Astronomie unerschöpflich. Wir mögen noch so weit in die Zukunft vorausblicken, es werden immer wieder neue Dinge passieren, neue Informationen auftauchen, neue Welten zu entdecken sein, und Leben, Bewusstsein und Gedächtnis werden immerzu weiterwachsen." (John D. Barrow: Die Entdeckung des Unmöglichen, Heidelberg-Berlin 1999, S. 324)
Alan Turing gelang über die Konstruktion der Turing-Maschine zum Beweis, dass es nicht-berechenbare Funktionen (Zahlen) geben muss, denn alle berechenbaren Funktionen können in eine stetige und endliche Kette von Einzelschritten aufgelöst und in einer universellen Turing-Maschine ausgeführt werden. Es gibt aber Funktionen, die nicht auf eine endliche Kette von Einzelschritten reduziert werden können. Dies betrifft zirkuläre (selbstbezügliche) Funktionen wie das Halteproblem (analog dem Beispiel der Kreter oben).
>> Der Ameise-Algorithmus (Rekursion):
Eine Ameise befindet sich ursprünglich auf einem zunächst weißen Raster und läuft in eine beliebige Richtung (in der Bilderserie nach unten). Wenn sie ein neues Feld betritt, so gelten folgende Regeln:
1. Ist das Feld weiß, so färbt sie es schwarz und dreht sich um 90 Grad nach rechts.
2. Ist das Feld schwarz, so färbt sie es weiß und dreht sich um 90 Grad nach links.Danach läuft sie auf das nächste Feld in der neuen Blickrichtung.
In den ersten 10.000 Schritten entsteht ein komplexes, chaotisches Muster. Danach bildet sich eine regelmäßige Struktur . Der Algorithmus gibt symmetrische Regeln vor, jedoch sind die entstehenden Muster asymmetrisch. Dieses streng deterministische Muster ist nur durch obige Anweisungen reproduzierbar.
zum Game of Live - der Klassiker der Zellulären Automaten siehe Wikipedia >>
Beispiel: >>
