[Playlisten] [Impressum und Datenschutzerklärung]

Gödels Unvollständigkeitssätze


CC-BY-NC-SA 3.0

Tempo:

Anklickbares Transkript:

die GödelschenUnvollständigkeitssätzeaus dem Jahr neunzehn hundert einunddreißigdas mal einzuordnendie allgemeine Relativitätstheoriewas hundert fünfzehnund die Entdeckung der Kernspaltungneunzehn achtunddreißigin die Periode Filtersum es eine Idee zu kriegen was sie setz überhaupt bedeutenKomma ganz vorne anich gehe aus von einer mathematischenTheorie ganz abstrakt gesprochendas wird nachher mindestens direkt mittig seinalso Plus und mal und die natürlichen Zahlenes könnte auch Geometrie seines Kantor ganz was anderes seinfang es mal ganz abstrakt anes sei eine mathematische Theorie gegebenund das wichtige für die man einen formalen Beweisprüferschreiben kannund zwar als Programm schreiben kannalso wirklich streng formalund dieses Programm soll auf einem Rechner laufen dürfen der beliebig viel Speicher hat oder genauer gesagt vor ich speichern beliebig nachrüsten kanndiese Programm simuliert sozusagen den Mathematikerder versucht einen Beweis nachzuvollziehenSchritt für Schritt exaktformal nachzuvollziehenund dabeieinen endlosen Vorrat an Papier beschreiben darfwenn ich einen Beweis formal nachvollziehenkann auf diese Art dann werde ich auch ein Programm dafür schreiben könnendieses Programm mit dem Teich analysiertGödel hatte einunddreißignatürlich noch nicht die Idee von heutigen Computerprogrammherdesganz anders formuliert das hier ist die moderne Interpretationvon dem was Goethe gemacht hatschreibt man auf ?? man sich so ein Programm vorstellenkönntedas meine Idee kriecht in der Tat so ein Programm müsste man schreiben können und kann man auch in der Tat schreibenfür die üblichen mathematischen Theorienich habe das mal in einer Fantasiespracheauf diesem bisschen WC aussieht oder Java oder sich Sharpeine Funktiondieses Programmschreibe eine Funktion hin die Funktion ist Beweisdass solche Funktion bekommenSie soll ein Beweis bekommen als Zeichenketteoder einen vermeintlichenBeweisund sie soll eine Aussagebekommendie vermeintlichvielleicht nur bewiesen wirddurch diesen Beweiszurück liefern soll sie ja oder neinein Burschenwertist der Beweisder vielleicht nur angebliche Beweiswirklich ein Beweis für die Aussage oder nicht?? können sich überlegen jetzt wie das im Prinzip ablaufen würdewas macht diese Funktion im Prinzipich werde mehr als man gucken ob dieser Beweis syntaktisch korrekt ist steht der irgendein Unsinnsowas wie?? es gibt fünf so dassieben X ist gleich maldas wäre offensichtlich Unsinndas will ich zuerst prüfensteht der syntaktische Unsinnwenn sie meiner Fantasiespracheaufgeschrieben ist der Beweis syntaktisch falsch istdann gebe ich natürlichsofort zurück das soll kein Beweis für die Aussage sein egal welche Aussage das wardie Syntaxüberprüfunghier kann laufen wie das der normale Compiler macht der guckt ja auch nach ob ein Programmsyntaktisch korrekt geschrieben ist das kann ich hier machen die Statik war sie ein Compilernicht ganz ein Compiler aber zumindest die erste Hälfte eines Compilersgar nicht gesagt was dieser Beweis sein soll dieser Beweis soll eine Liste an Formen seien die zum Schluss in der Aussage mündetdas checke ich jetzt auch noch ganz zu Beginn ist die letzte Formel aus dieser Liste wirklich die Aussageund wenn die letzte Formel nicht die Aussage ist dann akzeptiere ich das nicht als Beweisalso Returnfordsund jetzt gucken wir wirklich diese einzelnen Schritte an der Beweis soll eine Liste von Formen sein Formel inklusive logischer Ausdrückejetzt guck ich mir an ob das stimmig ist für jede Formelin diesen Beweisoder erhofften Beweismache ich folgendes ich prüfeob diese Formelaxiomist als eine der Grundannahmeoder ob ich die formlos eine der vorhergehendenFormenbeweist ?? eine Liste von Formen sein ?? herleiten kannwenn das für irgend eine Farbe nicht der Fall ist war das kein Beweis?? ich es aus Gegenteilfür jede Form ?? drin ist häufig auf das Gegenteilist diese Formelkeine Aktionund ist diese Formel nicht aus den vorherigenFormen aus diesem Beweis herleitbardafür brauche ich Schlussregelnwie kann ich von einen oder mehreren Aussagen auf eine weitere schließenund die Form ist nicht mit Schlussregelnherleitbaraus den vorherigenFormenMillimeter dieses geht auch das geht weiß ich au das was fauldas war kein Beweis in jedem Beweisschrittmuss das gehen die Formel muss ein Axiom sein oder sie muss aus den vorherigen Formen herleitbarsein mit Schlussregelndie beschreiben wie ich logisch denn von einem zum andern kommen darfentweder das eine noch das andere geht weiß ich also das war kein Beweis Returnfordswenn ich aber durch diese Schleife durch Komma ohne jemalsein Problem gefunden zu haben ?? jede Formel war ein Axiom oder die sich aus den vorherigen herleitendann weiß ich okay es hat funktioniertalles in Ordnung ich mache Ritter und trugenso könnte das prinzipiell aussehensoll jetzt durchaus noch ausformulierenwird fürchterlich werden aber im Prinzip ist an dieser Stelle klar es muss funktionierenich kann so eine Funktion schreiben für eine mathematischformalisierte Theoriemit dass sie hinhauen müssenman sieht nebenbei auch die Zutaten die man jetzt braucht was ist eine mathematische Theorieich brauche eine Art von Sprachefür Formelnso zu sagenich brauche Axiomemeine Grundannahmenund ich brauche Schlussregelnwie kann ich folgernvon ein was anderes folgern oder mehreren Sachen etwas anderes folgensolche Sachen wie wenn aus A B folgt und wenn aus B C folgt dann weiß ich aus A folgt auch Cdas für eine ganz einfache solche Schluss Regel davon brauche ?? Sammlung was ist alles erlaubtdiese Sachen hier SpracheAxiomeSchluss Regeldas sind die Zutatenzu einer mathematischen Theorie wenn man das so formalisiertwenn ich dir habe kann ich so einen Beweisprüferschreibenich kann dir hinten irgend eine Aussage in meiner Sprache hinschreibenhiervon sogar gab es Leerzeichen Kette eingebenweil ich diese syntaktische Prüfung habees egal was ich hier mache sieht man nun diese Funktion dieses Programmmuss immer hintenins Programm kann nicht endlos laufenes läuft ?? sehr langaber es muss irgendwann enden wir keine Schleife eingebautdie ?? Probleme machen könnte selbst diese Schleife hier ist irgendwann beendet ich gehe jede Formel in diesem Beweis durch eine Liste von Formen dessen endlich viele auch diese Schleife wird irgendwann endenalso diese Funktion endet immerdas gibt einem eine gute Idee was denn eine mathematische Theorie ist im üblichen Sinnedas muss man eigentlich jetzt genauer sagen aber die mathematischen Theorien im üblichen Sinne sind die von dieser Artinsbesondere kann ich dafür so ein Beweis früh verschreibenkann man sich überlegen was wollen wir eigentlich von so einer Theoriesind grundlegende Eigenschaftendie man verlangen könnteund was man sich anguckt ist einmal die Konsistenzalso wenn man so will die Widerspruchsfreiheitund einmal die Vollständigkeitjetzt Komma den Begriff Unvollständigkeitssätzeschon allmählich naheKonsistenzWiderspruchsfreiheithast folgendeswenn es einen Beweis gibtschon ein Beweisprüfergeschriebenkönnen's überlegen gibt es für irgendwas ein Beweisangenommen es gibt einen Beweisfür eine Aussage A dann heißt Widerspruchsfreiheites darf kein Beweis für das Gegenteil gebenegal welche Aussage das warwas ist also Inkonsistenzdas heißt die Konsistenz ist verletztich habe eine Aussage A irgendwo die beweisen kann und auch das Gegenteil davon kann ich beweiseneine Aussage Airgendeinewich ein Beweis für A selbstund auch noch einen für das Gegenteilim Anschluss gegen den indirekten Beweis dabei hatals das sofort das alles beweisbar ist insbesondere das nur gleich eins Beweis weißund wenn der indirekte Beweis erlaubt ist kann ich mit diesem einen einzigen Widerspruchalles begründenwas sie daraus schon wir wollen unbedingteine konsistente Theorieeine inkonsistente Theorie ist nicht allzu hilfreichdie zweite wichtige EigenschaftVollständigkeitdie Vollständigkeitist sozusagen die Konsistenz rückwärts gedachtwenn ich kein Beweisfür eine bestimmte Aussage habedann muss sich ein Beweis für das Gegenteil habenUnvollständigkeitheißt alsoich habe eine Aussagedie nicht beweisbar ist und das Gegenteil ist auch nicht beweisbar das heißt die Aussage ist weder beweisbar noch widerlegbardarum geht es natürlichzumindest beim ersten Unvollständigkeitssatzder erste Unvollständigkeitssatzsagt wenn die Theorie konsistentistdann ist sie unvollständigich kriege also diese beiden schönen EigenschaftenKonsistenzund Vollständigkeitnicht zusammenund der zweite Unvollständigkeitssatzsagtwenn ich die Konsistenzinnerhalb meiner Theorie beweisen kanndann ist die Theorie inkonsistentmit anderen Wortenwenn eine Theorie ihre Widerspruchsfreiheitselber beweisen kann danndie Theoriewichtige Fußnotedie mathematischen Theorien die man hier betrachtetmüssenstarkgroß genug seindie müssen hinreichend viel von der Arithmetik der natürlichen Zahlen umfassenich muss bestimmte Aussagen über natürliche Zahlen und Addition Subtraktionsmultiplikationbeweisen könnenim Verlauf selber gleich noch was das istalles nichts besonderes dessen Sachen die man erwartetdas kann man freundlich mit den Grundrechenartenarbeitender Trick ist folgender wenn die Theorie über natürliche Zahlen reden kann dann kann sie auch über Programme reden zumindest grundlegende Eigenschaften von Programmen redenund eine einfache Art die beiden Gödelschen Unvollständigkeitssätzezu beweisen ist dann man lässt diese Theorieüber Programme redendie Leute von dieser Funktionist Beweis gebaut hatdas gucken uns jetzt anjetzt kommt die geniale Idee von Gödelhat sich überlegt wenn ich es schaffefolgendesauszudrückenformal auszudrückeneine Aussage ich nenne sie mal gehendie besagtes gibt keinen Beweisfür diese Aussage gehenwenn ich es schaffe das überhaupt hinzu schreibenalso nicht zu sagen ob die wahr oder falsch ist so ?? bin ich überhaupt schaffe dieses formal hinzu schreiben in einer mathematischen Theoriedann muss irgendwas ganz fürchterlich knirschen dieser mathematischen Theoriedie Idee direkter konkreter machen ist folgendewenn es einen Beweis für G gibtdich ein Beweis dafürdass es keinen Beweis für G gibtdas wäre ein Widerspruch?? ist ein Beweis für das Gegenteil von G gibt als ein Beweis dafürdass es einen Beweisgibthätte ich gebe Wiesenaber gesagt es gibt keinen Beweis auch ein Widerspruchstellt sich ?? heraus man das etwas strenger betrachtet ist es nicht ganz so einfachaber erst mal ist die Ideees kann weder die Aussage G noch das Gegenteil beweisbar seinund damit ist diese Theorie unvollständigich habe eine Aussagesodass weder die Aussage noch ?? Gegenteilbeweisbar istGödel hat das neunzehn ein dreißig natürlich noch ohne die Ideedes heutigen Computers gemachter diese mathematische Theorie tatsächliche natürliche Zahlen übersetzte sogenannteGürtellinieFormeln werden zu monströs großennatürlichen Zahlenzu Beweisewerden zum monströs großen natürlichen Zahlendas aus heutiger Sicht etwas umständlichwas ich hier zeigen will ist eine Begründung die die Idee des Computers aufgreiftanalog zum Halteproblemtüren?? neunzehn hundert sechsunddreißigmit der Funktion des Beweis von eben schreibt man ein neues Programmeine neue Funktionnennen sie groß die für Gödelund sie liefert nichts zurücknimmt aber eine Zeichenkettein den ich mal groß Bder Job von diesem Programmgroß Gist es ein Beweis zu suchen?? dazu laufe ich alle Zeichenkettendurch dieser Variablen Bfange mit der leeren Zeichenkette aneine Schleifedannvon innen abgebrochen wird ich schreibe jetzt mein Endlosschleife Hinweis Schulungich möchte mit B alle möglichen Beweiseausprobierensolange bis ich einen gefunden habeich brauche jetzt eine Funktiondie mir über die nächste Zeichenketteliefert ich schreibe mal BS gleich nächster StringvonBdiese Funktion ist das trink soll so funktionierenwenn ich mit der Zeichenkette ABC reingehensollte Zeichenkette APdie rauskommenwenn ich mit AWD reingehensoll A B E rauskommenirgendwann bin ich bei AWZangelangtan so rauskommen A Cnullals erblicher weiterzählenwürde Zvon klein Z wieder ganz nach vorne das ist die Ziffer nullund von den Bein zweiterdass wir zu Ceinkamit Spatz NZZ angelangtund das soll dann werden nullnull null nullalso wie Zellen im Dezimalsystemjetzt aber nicht mit zehn Ziffern sondern mit allen möglichen Buchstaben die wir haben Beistrich ?? Baxter Buchstaben sowas wie für alle und es gibtdie Details sind auch ziemlich egalHauptsacheich gehe alle Zeichenketten durch Fischfang mit der leeren Zeichenkette anund diese Funktion sollte eine nach der andern Zeichenkette lieferndassjede Zeichenkette hier erreicht werden kann von dem Programmjetzt will ich wissen ob die Zeichenkette dieser aktuell dran istund diese Zeichenkette ein Beweis ist für etwaskompliziertereswennist Beweisdieses Bist dieses B ein Beweis für folgendes Dinghat das jetzt als Zeichenkette in das muss man dann nachher noch arithmetisch ausformuliertspäteressbare Zeichenkettewas möchte ich beweisen mit B für jede Zahl N läuft das Programm mit QuelltextPden habe ich vorher eingegebenund den werde ich jetzt hier im Original abdrucken alsobloß was in der VariablenP drin stehtund diesem Programm P gibt's noch ein Argument mitdas P ist eine Zeichenkette ich gebe diese Zeichenkette auch als Argument mit den Wert willigte eindie Frage ist jetzt läuft dieses Programm mindestensin Schrittewenn das der Fall istbeende ich mein Programm hier Mütterundgehe also insbesondere aus dieser scheinbar endlosen while-Schleife rausso noch mal was macht dieses Programm diese Funktion groß Ggeht alle möglichen Beweise durchund sucht ein Beweis für eine bestimmteetwas schräge Aussagewenn sie so ein Beweis gefunden hatdas Programm beendetMac einen Beweis finden läuft dieses Programm endlosauf dieses Programm hat eine Chanceauch nicht anzuhaltenanders als dieses hier ist Beweis wird auf jeden Fall halten es aber schon gesehenund wofür suche ich jetzt ein Beweisfür ein bisschen schräge Aussage hierich nehme die Zeichenkettehier oben übergeben wird lese die als Quelltextstelle mir das Programm mit dem Quelltext vorund gucken an was passiert dieses Programm mit dem Quelltext Pdem Gewicht genau diese Zeichenketteguckeläuft das Programmfür jede Zahl in mindestens N Schritte besagen läuft dieses Programmendloshält es nicht egal wie groß das NS deutsches Programm mindestens ein Schrittediese Aussage heißt nichts anders als das Programm hält nicht ?? ich suche ein Beweis dafürdass das ProgrammP aufgerufen mit dem Argument P nicht hältdas ärmliche Missing komisch formuliertder Vergleich klarer sehen was die mathematischen Hürden sindwahrscheinlich müsste man das ganze noch streng zu machen hier Backslashdoppelt Anführungszeichen untenund hier Backslash doppelt einfach sein Schreiben hier genausoum klarzumachen wo diese Zeichenkette P jeweils aufhört ?? ich für sich ganz übertragenund der Text hierder muss natürlich in Arithmetik übersetzt werdenplusminusmaldenn ich verlange das meine Theorievon der Arithmetik natürlicher Zahlen reden kannnicht gesagt sie soll von Programm reden kanndas Kung und später an offensichtlich wird es irgendwie geht ich kann dieses hier in plus minus malunnatürliche Zahlen übersetzenmein Programm gehen sucht also einen Beweis dafürdass das ProgrammP aufgerufen mit dem Argument P nicht hältund keinen Beweis gefunden wird läuft geendetwenn ein Beweis gefunden wirdendet gehenund jetzt kommt was kommen mussAnruf diese Funktionmit ihrem eigenen Quelltext aufals Ehemann nicht die Funktionaufrufenund ihr ihren eigenen Quelltext als Zeichenkette übergebenzwei mögliche FälleFall einses gibt den Beweis den wir suchennämlich dass für alle Zahlen ähmdieses Programmmit seinem eigenen Quelltext aufgerufen mindestens ein Schritte läuft wir sagen nicht hältFall zweies gibt keinen solchen BeweisLeerschritt ?? gar nicht ausführlich inder unten kommt dasselbe hinwiederumwenn es einen Beweis gibt für diese Aussagedann wird G von G haltendenbesuchen ja genauso einen Beweisnach endlich vielen Schritten ist mein Programm zu Ende kann jeden einzelnen Schritt aber mit Beweisen nachvollziehendiese Variable soundsoviel ist ist diese Variante soundsovielund hier wird was drauf addiert und so weiter und so weiterfalls Sie dies Programm Schritt für Schritt nach als Beweis und habe dann ein Beweis dafür dass es hältalso ein Beweis dafürdas nichtfür alle N das Programm mindestens ein Schritte läuftPunkt damit habe ich eine Inkonsistenzwenn es einen Beweis gäbedafür dass das Programmfür alle ähm mindestens in Schritte läuftkönnte ich einen Beweis findendas ist nicht für alle ähm mindestens ein Schritte läuft ich hätte eine Inkonsistenzanzugucken und den zweiten Fall anangenommen es gibt keinen Beweis dafürdass für alle N das Programm mindestens in Schritte läuftdas heißt mein Programm wird nicht fündig ersuchte nach diesem Beweis mein Programm wird nicht fündig es läuft endlos lange es hält nichtS kann ich mit Beweisenwieder Schritt für Schritt nachvollziehenaber natürlich nicht unendlich viele Schritte für endlich viele Schritte kann ich hiermit Beweisen nachvollziehen das man Programm immer noch nicht gehalten hatalso finde ich für jede natürliche Zahl Nein Beweisdas es nach den Schritten immer noch nicht angehalten hat das es also mindestens ein Schritte läuftgenau was ich hier überallgrün eingerahmt habeund jetzt wird das ganze etwas subtilhier oben steht ich habe ein Beweis für die Aussage für alleBild das Grüneund die unten habe ichfür allegibt es einen Beweis für das grüne das sind zwei paar Schuhe das muss nicht unbedingt dasselbe seinBeginn jetzt so vorwenn es keinen Beweis für diese Aussage gibtund ich die Vollständigkeitannehmevorgemerkt wennich die Vollständigkeitannehmedann muss es ein Beweis für das Gegenteil gebenalso nicht für alle Ngibt es und so weiterund das sieht schräg ausfür alle Türchenzahlen ähm kann ich die grüne Aussage beweisengleichzeitigkann ich beweisendass diese Aussagenicht für alle N auch Geldda muss was krumm seindas nennt Gödel eine Omega Inkonsistenzes ist nicht direkt ein Widerspruches ist keineechte Inkonsistenzist eine Inkonsistenzim unendlichen sozusagenfür jede endliche Zahl N kann ich die grüne Aussage beweisenich kann auch beweisen dass die grüne Aussagenicht für alle N giltdas kann man sich denkenPunktwie kann das seindas kann so sein dass diese Enz von den meine Theorie redetdass diese Enns unendlich groß sindgibt es in meiner Theorie unendlich große Zahlen dies nicht erfüllenman sieht das plötzlich ziemlich philosophisch dass es sich aber trotzdem alles noch mathematisch mit Hand und Fuß hinschreibenwas haben wir also zusammengenommenim ersten Fall habe Inkonsistenzim zweiten Fallhaben wir wenn wir Vollständigkeithabenobiger Inkonsistenzdas ergibtden ersten Unvollständigkeitssatzwie in Gödel ein ?? formuliert hataus OmegaKonsistenzalsowenn keine Omega Inkonsistenzvorliegt aus obiger Konsistenzfolgt die Unvollständigkeitwenn ich das hier verbietekann meine Theorie nicht vollständig seindas es noch nicht ganz der übliche Unvollständigkeitssatzdieses Omega hier nerv noch bisschenda Komma gleich noch draufwas den Beweis vom ersten Unvollständigkeitssatznach Gödelkann man zumindest anschaulich den zweiten Unvollständigkeitssatzbauen das war wenn die Theorie ihre eigene Konsistenz beweisen kann dann ist sie inkonsistentund guckt sich den Beweis vom ersten Unvollständigkeitssatzanund formalisiertihn in der Theorie selbstich nehme diese Begründung im ersten Fallübersetzte das in natürliche Zahlenein Argument rein in der Arithmetikund sehe danndie Theorie ihre Konsistenzbeweistdass sie oben nicht stattfindendenn dann wäre die Theorie ja inkonsistentalsoindirekter Beweisbeweist die Theoriedass es keinen Beweis für diese Aussage gibt in dieser formalisierten Form all das in Arithmetik übersetztdiese Aussage hinten ist aber nichts anderes als es gibt keinen Beweis ich finde keindie Theorie würde unsere Aussage beweisenund unsere Aussage würde sagenes gibt genau dafür keinen Beweiseine Inkonsistenzdas ist die Idee hinter dem Beweis vom zweiten Unvollständigkeitssatzder große Ärger ist wie man das jetzt hier alles in Arithmetik übersetztaber im Prinzip ist klar dass es gehen musses gibt sie noch ein kleines Ärgernis nämlichdas mit der OmegaKonsistenzoder Inkonsistenzhier möchte man einfach Konsistenz haben nicht Omega Konsistenzdas hat außer ein paar Jahre später hingekriegtneunzehn sechsunddreißigder ist das Omega losgewordenund klein Iirgendwann aufgeschriebeninspiriert von anderen Leutenwie man das schön mithilfe von Computerprogrammenzeigen kannGödel hatte die Idee formal auszudrückendass man eine bestimmte Aussagenicht beweisen kann und Wasserhat das Ganze noch raffinierter gemachtich hab das mal so hin eine Aussage eherdie folgende sagtfür jeden Beweis der Aussage er hatte diese Aussagefalls es einen gibt?? gibt's keingibt es einen kürzeren Beweis des Gegenteilsdas ist nun wirklichabgedrehtmit anderen Worten wenn ich nach ein Beweis für diese Aussage ersucheund einfindehabe ich vorher schon einen fürs Gegenteil gefunden?? records wieder nur drauf an diese Aussage formalauszudrückenmuss gar nicht entscheiden ob die wahr oder falsch ist es geht schon alles kaputt sozusagenwenn ich aber schaffe das hinzu schreiben in meiner Theoriedie DS folgende wenn ich diese Aussage beweisen kannhabe ich bewiesendass sie schon längst ein Beweis des Gegenteils hätte finden müssen ein Widerspruchwas wäre wenn ich das Gegenteil hiervon beweisen kann das Schreiben immerhin weil es komplizierter istwas ist das Gegenteil dieser Aussagedamit das hier fehlschlägtwenndann wenn es einen Beweis gibtgibt es einen kürzeren Beweis vondamit wenn dann fehlschlägtheißt das ich muss den Windteil erfüllendarf aber den dann Teil nicht erfüllen also es gibt einen Beweis der Aussageaber keinenkürzeren Beweis des Gegenteils dazuangenommen ich könnte das beweisendas Gegenteil von erdann wüsste ich es gibt ein Beweis von Rund keinen kürzeren Beweis für nicht eher ich habe aber einen Beweis von nicht erdas heißt jeder weiß von nicht er ist mindestens so lang wie der Beweis von Rich hätte auch den Beweis von nicht er schon finden müssenauch ein Widerspruchauf das es leichter zu formatieren?? Programm ausmacht ?? Training hatte das so ungefähr schon hingeschriebenich das jetzt machenun soll das Programm eine Zahl zurück liefernnennt er aber weiterhin eine Zeichenketteannehmendas Programm soll wieder nach einem Beweis sucheneiner Variablen B sollte stehenund hier wieder eine Schleife die vielleicht von Ihnen abgebrochen wirdeine Schleife die nach dem Beweis suchtoder jetzt immer gleich nach zwei beweisen suchtund zwar gucken wir erst mal ob unser B folgendesbeweistdas Programmmit Quelltext B diesen Texte eingefügtaufgerufenmit dem Argument P wiederendet mit null?? es endet hält und endet obendrein noch mit null ein konkreter WertKrokodilzeichenketteB hierfür ein Beweis istwenn das der Fall ist für uns raffiniert machengeb ich eins zurück als ich Suche nach ein Beweis ob null rauskommtausP aufgerufen mit Pund gebe dann aus mein Programm er die eins zurück nicht die nulldann natürlichdas nächste was ich gucke ganz logischist dieses B vielleicht ein Beweis dafürdass mein Programm nicht mit null endetalle dasselbe bla Blabla endet nicht mit nulldas heißt endet gar nicht oder endet mit einer anderen Zahl als null und wenn das der Fall ist gebe ich hier einen null zurückwenn meine Theorie vollständigistdann muss dieses Programm eher immer haltenich suche nach einem Beweis für eine Aussageund noch ein Beweis für das Gegenteilwenn meine Theorie vollständig ist muss eines von beiden irgendwann gefunden werdenund jetzt natürlich derselbe Trick wie bei Gödel ich rufe diese Funktion ehermit ihrem eigenen Quellcode aufund dann wird das hier natürlich gnadenlos Hakenbevor ich die eins zurückgebehabe ich schon längst bewiesendass er null rauskommen mussbevor ich den Null zurückgebe habe schon längst bewiesen das nicht in ?? rauskommen kannman im Detailich hoffe auf dieses Programm er mit seinem eigenen Quelltextdas Programm muss halten ??gerade gesehenwegen der Vollständigkeitder Gips nur zwei Möglichkeitenbeim halten es kann die null rauskommen oder die eins rauskommen was anderes war nicht vorgesehenwenn die null rauskommthabe ich ein Beweis gefundendass das Programm nicht mit null endetes wird also etwas bewiesenwas nicht wahr ist denn das Programm ergibt ja nullaber das ?? gleich noch was dazu uns geht's um das was bewiesen werden kannes mal nicht um das was Weissich finde aber jetzt natürlich auch ein Beweis dafür dass nur rauskommt ich kann dir Schritt für Schritt nachrechnenendlich vielen Schritten endet das Programmich kann Schritt für Schritt nachvollziehen was das Programm machtden dem ich das tue ich natürlich ein Beweis dafürdass nur rauskommtund das ist natürlich inkonsistentich finde ein Beweis das nicht rauskommt und ich finde eine weiß das du rauskommtden sprechenden zweiten Fall lohnt sich gar nicht das aufzuschreibenauch das muss zum Widerspruch führendamit habe den ersten Unvollständigkeitssatzin der üblichen Form Kühlwasseraus Konsistenzfolgt Unvollständigkeitdamit ist hier das störende Omega weg es geht nur um die ganz normale Konsistenzsollte noch andeuten was denn eigentlich die mathematische Leistung isteinerseits muss man auf solche Aussagenkommen sich schon Goethes ursprüngliche Aussageaber dann muss man vor allen Dingen in der Lage sein diese Aussagezu vom realisierenich muss mit mathematischen Mitteln hinschreiben können was heißt das eigentlich es gibt keinen BeweisGoethes hat geschafft das in Zahlen zu übersetzen?? Arithmetik natürlicher Zahlen zu übersetzenComputer heute ist das klarer man kann offensichtlich ein Programm schreiben das Beweisbarkeitprüftdas die erste Hürde die man überwinden muss und die zweite Hürde ist dieser Selbstbezugeine Aussagespricht von sich selbstGödel hat das anders als es jetzt vorgekommen ist nicht in dem ein Programm seine eigene Quellkode verarbeitetso und jetzt geht's darum was sind das einig bedeutetdie glücklichste Frage bei den kritischen Unvollständigkeitssätzenist wahrscheinlich was es denn jetzt bedeutetwie man das verstehen kannda kann man Tage und Wochen und Monate drüber diskutierenein paar erste Ideendiese selbstbezüglichenAussagen von Göbel und Ross war ich vorgeführt hatte zum Beweis die wirklich komisch wenn man die weder beweisen noch widerlegen kann naja was soll's mit den kann mir nicht allzu viel anfangen ?? es gibt aber auch handfeste Aussagen in der Mathematikdie man weder beweisennoch widerlegen kannsoll sein innerhalb der üblichen Mathematik wenn man sie als konsistentannimmtweder beweisen noch widerlegen kann ?? in die übliche Mathematik inkonsistentist kann ich alles beweisenund widerlegendiese Aussagen mit ABS gefunden worden war dem Gürtel die Unvollständigkeitssätzebewiesen hat diesen sogar teilweise von Gödel selbst gefunden wordendas erste ist die Kontinuumshypothesedie sagtjede unendliche Menge reeller Zahlengemeint es jede Menge mit unendlich vielen reellen Zahlenjede solche Menge hat entweder die Mächtigkeitder Menge der natürlichen Zahlen ist also selberoder die Mächtigkeitder Menge aller realen Zahlenes gibt nichts dazwischenkeine Unendlichkeitsstufesozusagenwas Mächtigkeitangehtzwischen den natürlichen Zahlen und den reell zahlenund was wir heute wissendie übliche Mathematik kann das weder beweisennoch widerlegenMann gibt es im Zweifelsfall als zweites Aktion dazu dazu gleich mehrdas nächste handfesteBeispielheißt noch wirklich Aktion das Auswahlaxiombetrachte eine Menge von Licht leeren Mengensagt das Auswahlaxiomes gibt eine Funktionmindestens eine Funktionfolgender Art egal welche Menge klein Mdieser Mengen groß M mich in meine Funktion stecke die Funktionfür solche Mengen ist das Ergebnis dann ein Elementvon dieser Mengenormalgroß Nist eine Menge von nicht leeren Mengen ich kann mir also die Mengen klein ähm angucken die in den groß Entrinnen sind und meine Funktionsoll solche Mengen verarbeitendie Elemente von groß Mund aus jedemvon diesem Elementvon groß Mwas wieder eine Menge ist ein Elementaus dem klein M Hausbeckenauswählenund eine Auswahlfunktionund auch das hier ist aus der üblichen Mathematik weder zu beweisen noch zu widerlegenman nimmt es weiß es ja schon typischerweisedazudas Auswahlaxiomund das ?? grinstefinde ich folgendesman kann ein Polynom?? superkompetentesPolynom konstruierenein Polynomvon mehrerenZahlen abhängt ein Polynom mit ganzzahligen Koeffizientendas folgende Eigenschaft hatdieses Polynomin ganzen Zahlen zu null gemacht werden kann also gibt es ganze Zahlen X einsbis X inso das wenn ich die Einsätze in mein Polynom null rauskommtdas hier ist weder beweisbarnoch widerlegbardaraus folgt natürlichwenn die übliche Mathematik konsistentist dann darf dieses Polynom keine Nullstellen habendenn sonst kann ich die Nullstelle einsetzen finde eine Lösung habe damit auch ein Beweisdas es eine Nullstelle gibtwenn man solche Aussagen hatwie die von Gödelund Rossa konstruierten oder wie die von gerade eben konnte nun Hypothese Auswahlaktionimmer solche Aussagen hatkann man damit neue Axiome bauenals gegeben so eine Aussage dass weder die Aussage selbst noch ihr Gegenteil beweisbar ist die Aussage ist weder beweisbarnoch widerlegbarman gerne dann einen Schalter aus ungefähr nicht so klar ist oder unabhängigals angenommen ich habe so eine Aussage A die weder beweisbar noch widerlegbarist dann kann ich die Aussage ganz schlicht zu meiner Theorie dazu nehmen und nichts wird kaputtgehenwie stört die Theorie ja sozusagen nicht besteht einfach danebenkann aber als neues Action dazu nehmen und kriegt keine neuen Widersprücheoderich genau das Gegenteil dazu nehmensie jedes Mal wenn ich so eine Aussage finde eine neue solche Aussage finde kann ich überlegen hoch nämlich das eine wurde nämlich das andere was wäre schön in meiner Theorieegal was von beiden nicht dazu nehme ich kriege keine neuen Widersprüchefalls ich überhaupt ?? Widersprüche haben sollteindem ich aber ein neues Action dazu nehme ändert sich diese Funktion ist Beweisdie prüft ja ob Axiome vorkommenPunkt das heißt ich kann wieder mit Gödel und Ross war eine weitere Aussage konstruierendie weder bewiesen noch widerlegt wirddas heißt in dem ich versuche meine Theorieso vollständig zu kriegenkann ich nicht gewinnen ?? es muss schon wieder eine weitere Aussage gebendie nicht bewiesen werden kann und nicht widerlegt werden kannwas man daraus lernt ist das es unendlich viele verschiedene Modelledas in der Mathematik so schön heißtwieComputer stell ich mir als Turingmaschinevordas heißt ich habe ein Rechenwerkund Logik darinund einen beliebig großen Speicher von dem ich immer nur endlich viel Platz benutzen darf natürlich sonst wird sowas unter siebenRechenwerk und Logik sind ein endlicher Automatstarte in einem Anfangszustandsinnvollerweisemit null bezifferteund dann wirdje nach dem was da so los ist er nach den Situationenfür das eine oder das andere oder wie auch immer passierendas natürlichaberwitzig viele Zustände für einen normalen Computeracht Bitsals Register auf dem Prozessor werden schon zwo hundert sechzehn fünfzig Zuständekann sich vorstellenbeim realen Prozessordas sozusagen fand das Millionen an Zuständenich mal jetzt hier nur meine Hand voll hin es geht dann irgendwie weiterdie Nummer dieses Zustands merklich als eine Zahl Zjetzt zum Speicherdass es bei Tuning das Bandich möchte mit natürlichen Zahlen arbeiten deshalb ist ein Bandungeschickt ich nehme zwei natürliche Zahlenund verstehediese beiden natürlichen Zahlenals Binärzahlenund als die linke und die rechte Hälfte des Bandssieht das dann aus die eine Zahl nennen Sie X ist die linke Hälfte des Bandes und die andere Zahl ist Ysondern an der legedie rechte Hälfte des Bandesgeht ?? Maschine musste eine Stelle von dem Band abfragt können immer dieses Bild hier das wird mit der kleinsten Wertigkeit von X und die Tormaschine muss das Band schieben können also vier von unten nach oben rein oder umgekehrt ich muss irgendwie so schieben könnendas letzte bitte unten raus da oben reinoder jedes abgefragtenBild oben raus und reinalso was soll der Speicher könnender Speicher sollvon oben nach unten schieben können?? soll von unten nach oben schieben könnenmöchte Abfragen günstig an dieser Stelle der Wert null oder der Wert einsund ich möchte hier ein Wert reinschreiben können den Wert null einschreibenkönnen oder den Wert eins reinschreiben könnender Zoll das Rechenwerksoll die Logik das Ion ansteuernwenn ich in einem bestimmten Zustand binkuck ich also nachstehtder null oder null einsan dieser Stelle die abgefragt wird und je nach dem verzweigtenStand eine null eins null oder null einsnulloder Neins glich für den Zustand zurück von mir ausnulleins nulleins wir könnten auch haben dass es in bestimmten Fällen nicht mehr weitergeht das unser Programm zu Ende ist Beistrich dass er zum Beispiel wegnehmekomme ich aus dem Zustand fünf nicht mehr weiter wenn hinten eine null stehtdas Programm ist zu Endedie Logik kann auch auf mein Speichereinwirkennatürlichimmer so was in den Speicher reinschreiben können oder den Speicher hin und her schieben können also je nachdem was hier so passiertKomma wenn der Wert null der hinten steht dann möchte ich so herum schiebenwenn ?? einshinten drin steht der möchte ich den Wert null reinschreibenwenn im Zustand einsnull stehtmöchte ich vielleicht nach eins reinschreibenund wenn dann einstehtmöchte ich vielleicht so rumschieben und so weiter und so weiterso kann diese Logik das Steuernhier sofort auch noch irgendwas sinnvolles passierenStücke Einstrinnen einer Schifffahrt so rumdass wir jetzt eine Turingmaschinemit einem endlichen Automatenundzwei natürlichen Zahlenals Speichermuss Aussagen wie das ganze gestartet werden soll was ist die Initialisierungin mein Speichern schreibe ich zum Beispiel als Zeichenkettedas Programm reinwas ausgeführt werden soll und ?? Turingmaschineund ich schreibe das Argument rein was ich mein Programm mitgebendas heißt ich weiß was ganz zu Beginn X und Y sindund was Z ist drittes nullund dann kann ich Schritt für Schritt weitergehenhier in meinem endlichen Automaten nachgucken was passieren mussdamit nach zweiundvierzig Schrittenist der Zustand Z zwoundvierzigwohnt dieser Wert hier ist X zweiundvierzigund ?? Wetter und nicht Y zweiundvierzigda kann ich in meinem endlichen Automaten nachguckenwas denn der nächste Zustand ist und was ich meinem Speicherantun muss ich Regecest dreiundvierzig HausX dreiundvierzigund Y dreiundvierzigdas geht natürlich auf dieselbe Art von dreißigstensund Wien vierzigstenoder vom Noten zum ersten und so weiterund so weiterversuche ich dieses hierzu kritisierenmit den Grundrechenartenhinzuschreiben?? die Idee ist ein wahnsinniggroßes Produkten zu schreibenerster Faktormal zweiter FaktorMal und so weiteran das Millionen Faktorengleichnullhabe ich eine arithmetische Bedingungvon der ich weißdas eine der Klammern einer dieser Faktoren hierder muss Null sein binbestens einer es wird gleich auch nur höchstens eine null sein Könnenhinter dieser Faktoren beschreibt einen der Pfeilein den Sautomatenzum Beispiel könnte ich mir folgendes anguckenbin ichSitze Zustands nurwenn ich in Zustand mit der Nummer dreizehnnur dann wird das hier nulljetzt wüsste ich gerne ob in dem Xeine gerade Zahl stehtob das Bild was ich untersuche gleich null istdas Gericht damit hin und wenn ich hier noch dazu schreibe es gibt eine ganze Zahl meine ich hier damit abermit folgender Eigenschaftich untersuche ob X zweiundvierzigdas Doppelte einer ganzen Zahl ist wenn jakann dieses Quadrat ?? null werden wenn nein kann dieses Quadrat niemals null werdenmit anderen Worten diese Summe hierwird dann und nur dann nullwenn ich im Zustand mit der Nummer dreizehn binund wenn Xeine gerade Zahl ist und hier das richtige Ausblickewenn das der Fall ist ich bin im Zustand dreizehnund hintenund mein Text endet mit einer Nullstelledich Abfrageist das null in das der Fall ist möchte ichin den Zustand hundert gehen also Z dreiundvierzigminushundert ins Quadratich möchte dass der Wert von X unverändertbleibt X dreiundvierzigminus sechsundvierzigins Quadratdiese Differenz soll null werdenund ich möchte dass der Wert von Y unverändert bleibtschon dreiundvierzig bis zwoundvierzig ins Quadratdieser vorderste Faktorwird dann und nur dann nullmit dem Zustand Nummer dreizehn bindashintere Bild von Xeine null istund ich danach eine Zustandhundert geheund X und Y unverändert bleiben dann und nur dann bitte erste Faktor nullVerbandsverdeutlichungnoch in weiteren Faktor hinwenn der Zustandder mit der Nummer achtundneunzigistund wenn das letzte Bit ungeradeistminus zwei A minus einsdas kann dann null werdennur dann null werden wenn X wahnwitzig ungerade istzeigte dieses A von dem es gibt ein paar euch kein neues es gibt davorwas möchte ich dann wenn das der Fall ist möchte ich in den Zustand sieben gehen und möchte vielleicht mal schiebenX dreiundvierzigminus eins Quadratin Ar stehen die vorderen Bits von X zweiundvierzigdrinextra in vierzig hat jetzt noch die vorderen Witz ich bin hinten ein Bit losgewordendas Bild was ich losgeworden bin ist eins das muss dann Y reinmuss Y gegenläufig verschiebenals ob sondern vierzig minus zwei hundert Y zwoundvierzigminus einsQuadrat und hier noch die Klammer zuY ist das was es vorher war Meister links geschobenund noch mit eins dran was aus X rausgeflogenund so weiterund so weiterfür jeden Fallin dem endlichen Automatenwas wir hier habenist ein absurdes Sammelsuriumvonplusminusganze Zahlenmultiplikationquadratischen Multiplikationund hier Multiplikationes ist ein Polynomin das Polynom setzt sich einZ zweiundvierzigX zweiundvierzigY zweiundvierzigdieses Ahrsetzt sich ein für die Werte nach dem Schritt also Z dreiundvierzigX dreiundvierzigundY dreiundvierzigdas ist ein Polynomaber natürlich ein absurdkompliziertes Polynomhabe ich einen Schritt übersetzteinen Schritt ?? kritisiert sozusagenwas sich aber meditieren will ist die Aussage dass das Programm mindestensN Schritte läuftein ProgrammmitArgumentQläuft mindestens ein Schrittejetzt versuche ich diese en Schritte nachzuvollziehenmit meinem Polynomund stehen Z und X und Ynach dem ersten Schritt habe ich ein Z einsein X eins und ein Y einsetliches als natürliche Zahlen keine ganzen Zahlenund so weiterund so weiterund nach dem enden Schritt habe ich ein Z N einX Nund ein Y ähmnoch diese Arztesvariablenfür jeden Schrittnämlich mal eines dieser Hilfsvariablenreinmuss für jeden Schritt dieses Polynomnull sein war die Bedingungich fange an den Zustand nullin X steht das ArgumentQund in Y steht das Programmeinst die Hilfsvariableund nach dem ersten Schritt habe ich Z eins X einsY eins das muss Null sein undvon Z eins X einsY eins mit A zweiZ zwei X zweiY zweidas muss neu sein undund und und der letzte im Bunde wird seinZ ähm minus einsX ähm minus einY N minus einsA N Z N X ähmY N das muss neu seindas bedeutet es mindestens N Schritte zu laufen?? Funktion F vier sorgt für jeweils einen Schritt oder sollte Sankt ihren Sohn L vier prüft jeweils einen Schritt in dem endlichen Automatenguckt hier im Speicher nachob auch das richtige passiert istim Prinzipsind wir seitlich fertighier steht eine arithmetisch logische Formelund kein Programm mehrwas jetzt noch ein bisschen nervt ist das hier die Anzahl der Variablenvon N abhängtschöner wäre eine einzige Formel zu haben in die eine feste Zahl an Variablen drin steht auch das klappt sogar nochsich erst mal an von wo bis wo diese ganzen Variablen hier laufenwie gesagt er soll natürliche Zahlen ab null seinversicherten untere GrenzeZ ist ein Zustanddas heißtwenn ich die Zahl der Zustände weißüber die MakrosZund ich doch mal die Zustände sollen sein von null bis groß Z minus einshabe ich eben groß ZZuständedieses Z einsist kleiner als groß Z dieses Z NS kleiner als groß Zda kuck ich mir also immer nur eine feste Zahl an Zuständen anmit dem X und Ygleich mit den Aaswitzenbisschen kompliziertervor dem ersten Schritt ist das X gleich dem Coupin dem einen Schrittkann ich aber das X dann höchstens um ein Bit verschieben und hinten ?? eins rein schiebendas heißtes X einsist auf jeden Fall kleinerals zwei Q plus zweiim nächsten Schritt kann das X einshöchstens um einen Schritt nach links Wandern und hinten noch nach eins rein bekommen das sagt mir wasüber X zwei und so weiter und so weiterund das weiterverfolgtsieht man dass dieses X Nkleiner sein muss als zwei hocheinmalQ plus zwei UNdieses Kuh wird maximalähm mal nach links verschoben also mal zwei hoch en und dann kann ich dahinter lauter Einsen packen lauter Einsen während zwei Wochenminus einssteht mit kleiner Zeichen ich gehe noch ein zweiterY analogschreibe jetzt kann ich ihn mit dem P natürlichund für diese Aasmuss man sich was kluges überlegendie werden mal bei X mal bei Y vorkommenund sind sozusagenimmer die Hälfte von X und Y plus minus eins das heißt auch diese Asia werden irgendwieauch ganz fürchterlich gedeckt seinund jetzt kommt der große Kunstgriffdamit die Anzahlder Variablen hier nicht von N abhängtich gucke mir ?? nur das Z an ich habe ähm von diesen setzjedes davon ist gedeckt giltder Gedanke ist ich konstruiere eine einzige Zahlsozusagen im Zahlensystemmit der Basis Zstellen uns das im Zehnersystemvor wenn ich so eine Zahl im Zehnersystemhabedann kann ich daher fünf einzelneStellen draus machen fünf Zahlen fünf Ziffern soll ich sagen ?? von null bis neunwenn ich das nicht mit null bis neun machesondernmit null bis Z minus eins machekann ich soundsovielquasi Ziffern von null bis Z minus eins generierendas es mein Gedanke ich baue eine große Zahlund generieren daraus Ziffernaber nicht im Zehnersystemsondern im System mit der Basis Zeinetypischerweise monströs große Zahl jetztaber immer noch gedeckseltemich die Zahl der ZuständeHochentschlusseinsund daraus destilliert ich jetzt sozusageneinzelneZiffernfür jede einzelne Ziffer kann ich mit diesem für alle jetzt hier für jede einzelne Ziffern sozusagen da dringeneriere ich die einzelne Ziffer und setze sie dann ein für jede Ziffer schreib das mal HindusAussehen soll mein Polynomwird sicher ein Z XY Hartz Z XYsoll Null seinmuss aus diesem Zfür den Schritt mit der Nummer Kzwei verschiedeneChats generierendas Vorher und das Nachher VorherNachherdas dann einfach aufeinanderfolgendeZifferndiese Zahl ZZelle lege ich quasi in Ziffernder set Strichsteht mit derKartenpotenzvon dem groß Zund das Z zwei Strich steht mit der K plus ersten Potenz von den groß Zhabe ich alle Ziffern die noch davor Komma die sind soundsovielmaldie K plus zweite Potenz von dem groß Z lächelnder Smiley U und hinten habe ich noch die Ziffern dahinternennen die dann mal V zusammen genommenund jetzt muss ich diese Zerlegungnoch mit zum Ex istins Konto dahin bastelnes gibt alsohier vorne diese somuss ich weiter vorsichtig sein Hauptsache es ist eine Zahl ab null aufwärtsich kann sehr großzügig sein bei der oberen Grenze ich gebe einfach mal an groß Zhoch N dann bin ich auf der sicheren Seite auch wenn ich hier Id viel zu viel machendann dieses setzt Beistrichdass es ja eine Ziffer die ist maximalgroß Z minus eins unbeschreibliche kleiner groß Zdasselbe gilt für Z strichdieses V Hindernis maximal jedoch kamen minus einsdamit habe ich das Z erledigtund kann sich jetzt vorsichtig vorstellen das mit X und Y und mit Ahrwas ähnliches passieren musses ist ein bisschen ekliger sich die Grenzen ausdenktund sich hier außer denken was man statt groß Z einsetztaber im Prinzip muss das Funktionierenals ihr gerissener weiter mitXund Y und A und hier geht's ?? eben noch weiterund hier geht's entsprechend weiterund hier kommt dann sowas wie X Strich Y StrichhaarX BeistrichAbsatz Beistrich reinentweder noch eine Sachedie Anfangsbedingungich muss noch fordernFankagleich Null istund ich dann den ersten Schritt machedann mussZ strich gleich null sein ich möchte im Zustand null startenund es muss X strich gleich dem Argument sein und es muss Y strichgleich dem Programm seinjetzt habe ich das wirklich vernünftig ?? kritisierthier steht eine feste Zahl an Konturendenkt nicht mehr von dem en abes gibt es gibt es gibt für alles gibt es gibt es gibt und so weiteralles Sachen die man mit der elementaren Arithmetikerledigen kannwas am Rande der spannend ist bei allen diesen Konturen hier stehenendliche Schranken trennen keine der Konturen läuft über die gesamten natürlichen Zahlenwas ich jetzt erreicht haben diese Formelnlogische Formen logisch arithmetische Formeldie würde man jetzt hier oben einsetzendas ist der grüne Kastender wird ersetztdurch so einen arithmetisch logischen Ausdruckund mein Beweissuchersuchtennach etwas aus der Arithmetikdas ist diese Übersetzung hierin die Theorie genügend viel von arithmetiknatürlichenZahlen umfasstdann kann ich das tun was ich gerade vorgeführt habe auch etwas über Programme aussagenund die man gesehen hat es nichts besonderes von der Arithmetik der natürlichen Zahlen die man einbauen musses werden extrem komplizierte Formelnwenn ich wirklich alles hinschreibenwas ich da ebenso Hände wird angedeutet habe