Was ist ein Algorithmus?

14. April 2012 von Josef Honerkamp in Begriffe der Physik

Vor kurzem hörte ich, wie ein Anwalt mit großer Erfahrung und langer Praxis über einen juristischen Fall berichtete, in dem es um eine so genannte Erfindungsbenennungsklage ging. Im Mittelpunkt stand eine technische Erfindung, die im wesentlichen auf der Entwicklung einer Software beruhte, und diese wiederum fußte auf einer bestimmten mathematischen Einsicht und einem daraus abgeleiteten Berechnungsverfahren.  Eine Firma, die diese Erfindung verwerten wollte, hatte sie zum Patent angemeldet, ohne aber die eigentlichen Erfinder und Entwickler der Software, nämlich Mitarbeiter einer anderen Firma in der Patentschrift zu nennen. Beide Firmen waren über diese Software ins Geschäft gekommen, waren dann aber in Streit geraten über die Form der Verwertung.  Solch ein Fall gilt unter Juristen als exotisch. "Wer von ihnen weiß schon, was ein Algorithmus ist." hieß es.

Mir wurde wieder bewusst, wie ein gelehrt klingender Name eine Hürde für ein Verständnis aufbauen kann, wie er aber immerhin auch dazu führt, dass man die Bedeutung eines Begriffes nicht unterschätzt.  So will ich hier versuchen, diesen Begriff etwas zu beleuchten, ihm seine Unnahbarkeit nehmen - aber auch seine Tiefen andeuten.

Einige Algorithmen kennt jeder

Zunächst einmal: Ein "Algorithmus" ist nichts anderes als ein Berechnungsverfahren.  Jedes Kind lernt in der Schule einen Algorithmus, wie man z.B. "schriftlich"  ganze Zahlen addiert, multipliziert oder dividiert. Früher gab es für solche einfachen Rechnungen ein Rechenbrett oder Abakus; dabei lernte man auch gleich, dass solche Berechnungen automatisierbar sind und Maschinen übertragen werden können. Ich vermute aber, dass dabei nie gezeigt wird, dass diese Algorithmen auch wirklich das leisten, was sie sollen, dass also z.B. beim "schriftlichen Dividieren" wirklich immer das richtige Ergebnis heraus kommen muss.  Die Idee, dass hinter solchen Berechnungsverfahren eine abstrakte mathematische Aussage  steht und dass man beweisen muss, dass das Berechnungsverfahren ganz allgemein diese Aussage widerspiegelt, wird in der Regel wohl nicht zum Thema gemacht. Man lernt, so zu verfahren, und freut sich bei jeder einzelnen Überprüfung, dass es stimmt.

Diese Algorithmen für die Grundrechenarten in unserem Zehnersystem waren natürlich nicht die ersten Algorithmen, die die Menschen kannten. Der griechische Mathematiker Euklid hatte schon etwa um 300 v.Chr. einen Algorithmus entwickelt, um den größten gemeinsamen Teiler zweier natürlicher Zahlen zu finden (siehe Wikipedia: Euklidischer Algorithmus) . Hintergrund dafür war, dass er die Längen zweier Linien als Vielfaches eines gemeinsamen Maßes darstellen wollte.  Das Wort "Algorithmus" ist aber erst nach 800 entstanden, als man sich beim Rechnen immer auf das Lehrbuch "Das Buch der Addition und Subtraktion entsprechend der hinduistischen Rechnung" von Muhammed Al-Khwarizmi bezog, in dem dieser als Erster das hinduistische Dezimalsystem einführte. In der lateinischen Übersetzung hieß es dann "Liber Algorismi de Numero Indorum" und es begann mit dem Satz "Dixit Algorismi". (Das Hauptwerk dieses  islamischen Astronomen und Mathematikers hieß übrigens al-Jebr, woraus unser Name "Algebra" entstanden ist. )

Mathematische Gleichungen und Probleme sind also seit jeher untrennbar mit Berechnungsverfahren verbunden, und im Laufe der Zeit begannen die Menschen auch danach zu streben, solche Verfahren automatisch abarbeiten zu lassen (siehe Wikipedia: Rechenmaschine).

Algorithmen für mathematische Probleme

Heute spielen elektronische Rechner in allen Bereichen des öffentlichen und privaten Lebens eine bedeutende Rolle, sei es als Großrechner oder im Smartphone. Jeden Tag werden in der Forschungsabteilungen der Wissenschaft und Industrie unzählige Algorithmen für alle möglichen Probleme entwickelt und geprüft. Diese stützen sich auf grundlegende Algorithmen der angewandten Mathematik und theoretischen Physik, mit denen man Differential- und Integralgleichungen lösen, das Maximum von Funktionen finden, stochastische Prozesse simulieren oder Schätzer in der Datenanalyse berechnen kann. Sie alle bestehen meistens aus sehr vielen Berechnungsschritten, was sich auch in der Menge der Anweisungen an die Recheneinheit eines Computers niederschlägt und damit auf die Länge des Programmcodes. Natürlich muss der Algorithmus selbst so gut studiert sein, dass man weiß, was er leistet und wie genau das gegebene Problem gelöst wird. Es muss aber auch die Umsetzung des Algorithmus in die Liste der Anweisungen an den Computer richtig sein. Das alles erfordert viel Wissen und harte Arbeit am Detail eines vorliegenden Problems.  Nicht umsonst stellt solch ein Algorithmus zur Lösung eines ihrer speziellen Probleme für jede Firma einen großen Schatz dar, häufig einen entscheidenden Wettbewerbsvorteil.  

Algorithmen ohne mathematische Probleme

Somit  ist ein Algorithmus also zunächst ein Berechnungsverfahren für ein mathematisches Problem. Dieses kann durch eine Gleichung gegeben sein oder durch eine Frage nach z.B. der Teilbarkeit oder dem Maximum einer komplizierten Funktion. Mit einem solchen Zusammenhang zwischen einem mathematischen Problem und "seinem" Algorithmus war ich aufgewachsen. So war ich höchst befremdet, als ich irgendwann in den 70er Jahren von den "zellulären Automaten" hörte (siehe Wikipedia: Zellulärer Automat) . Das war ein Berechnungsverfahren "pur", keine mathematische Gleichung dahinter, kein solches Problem -  dafür aber der Anspruch, dass die Natur sich eigentlich so verhält und unsere schönen mathematisch formulierten Theorien nur eine Art poetischer Einkleidung darstellen sollen.

Solch ein zellulärer Automat besteht aus vielen Zellen, die in verschiedenen Zuständen sein können, und man gibt nur die Regeln dafür vor, wie bei einem Berechnungsschritt der Zustand jeder Zelle in Abhängigkeit von den Zuständen der Nachbarzellen zu ändern ist. Besonders berühmt wurde dabei das "Game of Life" (siehe Wikipedia: Conways Spiel des Lebens).  Das verblüffende an diesen zellulären Automaten ist, dass schon mit wenigen einfachen solcher  Regeln der gesamte Automat im Laufe der Berechnungsschritte höchst komplexe Strukturen zeigen kann. Wieder ein Beispiel von Emergenz:  Jede Zelle hat nur ein einfaches Verhaltensrepertoire, das Zusammenspiel führt aber zu ganz neuem Verhalten, das auch mit ganz anderen Begriffen zu beschreiben ist.

Mit einem zellulären Automaten wird eigentlich nichts wirklich berechnet. Er ist aber ein Algorithmus, eine Folge von Anweisungen. Stets ist bestimmt, was als nächstes zu tun ist. Und sogar bei einem stochastischem zellulärem Automaten ist die Vorschrift eindeutig: an bestimmten Schritten muss man würfeln, d.h. eine Zufallszahl generieren (nach irgendeinem anderen Algorithmus). Offensichtlich ist das Konzept eines Algorithmus allgemeiner als das einer physikalischen Theorie. Man hat nur den Eindruck, dass bei einem reinen Algorithmus "der Sinn" fehlt.  Oder wird der vielleicht nur von uns Menschen in die Natur hinein gelegt?  Ein Stein, der zu Boden fällt, richtet sich ja nicht nach dem Gravitationsgesetz, er fällt einfach. Aber wie sollen wir andererseits auf die richtigen Algorithmen für Naturvorgänge kommen, wenn wir uns nicht an fundamentalen Prinzipien und Gleichungen orientieren können?  Und da es diese nun doch zweifellos auch gibt und - vor allem - nicht beliebig zu haben sind, müssen sie auch wohl irgendetwas in der Natur widerspiegeln.

Wie weit reichen algorithmische Verfahren?

Tatsache ist aber, ein Algorithmus ist nicht allein als etwas zu betrachten, was sich aus einem mathematischen Problem ergibt. Er ist zu einem zentralen Begriff der theoretischen Informatik geworden. Hier stellt man sich Frage, wie weitreichend das algorithmische Verfahren ist, welche Probleme man mit Hilfe eines Algorithmus (und damit mit einem Automaten) prinzipiell lösen kann (siehe Wikipedia: Berechenbarkeitstheorie).  Man nennt das Problem dann auch entscheidbar. Entscheidbar und berechenbar ist ein Problem offensichtlich dann, wenn man einen Algorithmus finden kann, der irgendwann zu einem Ergebnis gelangt. Natürlich haben wir alle zunächst viele entscheidbare Probleme kennen gelernt, z.B. die oben genannten Probleme im Rahmen der Grundrechenarten: "Wie oft ist eine Zahl in einer anderen enthalten?, usw.  Ein jüngst aktuelle Frage war, wie viel Zahlen muss man in einem Sudoku mindestens vorgeben, damit es überhaupt eine eindeutige Lösung geben kann. Mit roher Rechnergewalt hat man es heraus bekommen: 17 Zahlen sind es. (Eine Sammlung von Sudokus mit nur 17 Zahlen findet man in    http://mapleta.maths.uwa.edu.au/~gordon/sudokumin.php.)

Interessant ist aber die Frage, ob es Probleme gibt, von denen man sagen kann, dass sie prinzipiell nicht entscheidbar sind. Der englische Mathematiker Alan Turing führte dazu erst einmal ein abstraktes Modell für einen beliebigen Algorithmus ein sowie das Konzept eines Automaten, der dieses ausführt. Ein solcher Automat, auch bald Turing-Maschine genannt, kann nur wenige unterschiedliche Operationen ausführen; mit diesen aber hat man die Möglichkeit, die Ausführung eines jeden Algorithmus als eine Folge von solchen Operationen darzustellen. Bei einer Lösung des Problems hält die Maschine an. Würde man ein algorithmisch nicht entscheidbares Problem einer Turing-Maschine anvertrauen, würde diese also nie anhalten.

Aber gibt es denn überhaupt nicht entscheidbare Probleme, also solche, die durch keinen Algorithmus gelöst werden können, so dass eine Turing-Maschine nie anhält?  Seit 1931 weiß man aufgrund der Arbeiten von Kurt Gödel, dass im Rahmen eines  jeden (hinreichend reichhaltigen) formalen Systems Aussagen formulierbar sind, die man als wahr erkennen kann, die man aber nicht mit den Mitteln des Systems beweisen kann (siehe auch den Beitrag: "Innenwelt und Außenansicht").  So ist z.B. die Widerspruchsfreiheit eines Systems von Axiomen nicht durch die Axiome alleine beweisbar. Ja, es kommt sogar noch schlimmer: Man kann nicht einmal immer entscheiden, ob ein Algorithmus überhaupt eine Entscheidung liefern kann. Will man also mit einer Turing-Maschine, sprich einem Algorithmus, die Frage beantworten, ob ein Algorithmus ein bestimmtes Problem lösen kann, so wird es vorkommen, dass die Maschine nie anhält. So hat man also auf einem Gebiet, in dem man strenge und verlässliche Beweise führen kann, gezeigt, dass man nicht alles beweisen kann, und dass man nicht einmal immer eindeutig entscheiden kann, ob man etwas beweisen kann. Das war ein ungeheurer Fortschritt.

Was ist das nicht-algorithmische Denken?

So sehr also algorithmische Verfahren unsere Welt in Naturwissenschaft und Technik bestimmen, so unverzichtbar die Rechenautomaten und Computer heute in der modernen Welt sind, es gibt anscheinend noch andere geistige Tätigkeiten, die uns Menschen befähigen, in dieser Welt zu überleben. Da braucht man gar nicht Gefühle wie Freude und Trauer ins Feld zu führen, schon beim mathematischen Schließen müssen wir uns auf Einsichten verlassen, die wir nicht im Rahmen eines Axiomensystems beweisen können. Wir können die Schlüssigkeit von Argumenten bewerten, etwas "verstehen" und als wahr erkennen, obwohl wir es nicht algorithmisch beweisen können. Fügen wir solche Einsichten zu dem Axiomensystem hinzu, um so zu einem größerem  System zu gelangen, werden wir wieder wahre Aussagen machen können, die aus diesem nicht algorithmisch gefolgert werden können. Wir haben das Problem nur auf eine höhere Ebene verschoben.

Unser Gehirn ist also nicht mit einem Computer zu vergleichen, zumindest nicht mit einem der heutigen Computer. Ob wir dieses meta-algorithmische Denken irgendwann einmal so "verstehen", dass wir es auch automatisieren können, vielleicht sogar auch als versteckten Algorithmus erkennen, kann man heute nicht sagen. Es gibt noch viel in uns zu entdecken. 


28 Kommentare zu “Was ist ein Algorithmus?”

  1. Dr. Webbaer Antworten | Permalink

    Algorithmen

    Herr Honerkamp, wieder ein sehr schöner Blog-Post, danke!

    Vielleicht noch hierzu:

    Seit 1931 weiß man aufgrund der Arbeiten von Kurt Gödel, dass im Rahmen eines jeden (hinreichend reichhaltigen) formalen Systems Aussagen formulierbar sind, die man als wahr erkennen kann, die man aber nicht mit den Mitteln des Systems beweisen kann (siehe auch den Beitrag: "Innenwelt und Außenansicht").

    Manche fragen sich, ob die oben zitierte hinreichende Reichhaltigkeit nicht gerade das Abgrenzungskriterium ist, das Systeme unentscheidbar macht. - Gäbe es hierzu vielleicht etwas zu ergänzen?

    MFG
    Dr. Webbaer

  2. David Antworten | Permalink


    ob die oben zitierte hinreichende Reichhaltigkeit nicht gerade das Abgrenzungskriterium ist, das Systeme unentscheidbar macht.

    Eine merkwürdige Frage. Wofür sonst sollte die Reichhaltigkeit denn hinreichend sein?

  3. Dr. Webbaer Antworten | Permalink

    @David

    Wenn Sie genau hinlesen, werden Sie feststellen, dass die Frage eine andere war.

  4. Wilhelm Druben Antworten | Permalink

    hinreichend reichhaltig

    Die Ergänzung "hinreichend reichhaltigen" bezieht sich wohl darauf, dass Gödel (so weit ich weiss) zunächst bewiesen hatte, dass die Formale Logik vollständig ist. Zu seiner grossen Überraschung ist ein System, das zumindest die Arithmetik umfasst aber nicht vollständig und... wiederspruchsfrei zugleich.
    Ist es nicht so? Leider bin ich kein Fachmann, aber schon in einfachen Computerprogrammen ist das Halteproblem Alltag.
    Philosophisch interessant ist diese Aussage, weil sie dem Anspruch der Mathematik die einzige Sprache der Natur zu sein, den Boden entzieht, nicht aber dem Anspruch, dass erst durch die Mathematik viele tiefe Einsichten in die Natur erst möglich werden, wie ich selber mehrfach erfahren durfte.

  5. Dr. Webbaer Antworten | Permalink

    Systeme

    Erst einmal ist es ohne weiteres möglich Systeme zu entwickeln, die entscheidbar bleiben. - Man hat das nicht getan, und dafür gab es etliche Gründe...

    ...denn die Mathematik ("Kunst des Lernens") benötigt zwischengeschaltet zur Natur das Erkenntnissubjekt, so dass die Mathematik nicht die Sprache der Natur sein kann.

    Ansonsten war's natürlich eine Art Themenwunsch. Dieser Schreiber interessiert sich bspw. dafür, ob die Nicht-Entscheidbarkeit bestimmter Systeme kategorisiert ist. Oder dafür, ob Gödel wirklich überrascht war. :-)

    MFG
    Wb

  6. Chrys Antworten | Permalink

    @Dr. Webbaer

    »Manche fragen sich, ob die oben zitierte hinreichende Reichhaltigkeit nicht gerade das Abgrenzungskriterium ist, das Systeme unentscheidbar macht. - Gäbe es hierzu vielleicht etwas zu ergänzen?«

    Worauf genau zielt denn Ihre Frage ab? Sie sprechen dabei Unentscheidbarkeit an, die zitierte Textstelle bezieht sich jedoch auf Unvollständigkeit. Das sind schon zwei verschiedene Dinge, beispielsweise kann ein formaler Kalkül vollständig und dennoch unentscheidbar sein.

    »Herr Honerkamp, wieder ein sehr schöner Blog-Post, danke!«

    Damit haben Sie dann allerdings recht.

  7. Martin Holzherr Antworten | Permalink

    Selbstgenügsame Algoritmen,z.B.das Leben

    Schon der zelluläre Automat zeigt, dass es zweckfreie Algorithmen  gibt, denn wenn ein Zellulärer Automat einen Zweck hat, dann den, sich selbst am "Leben" zu erhalten. Gibt es keinen Folgezustand mehr, der etwas ändert ist das System tot. Wenn Mathematiker sich mit Beweisen, aufstellen von Axiomensystemen etc. Beschäftigen, so lässt sich ihr Vorgehen nicht sinnvoll als Algorithmus fassen. Und trotzdem werden alle Lebewesen (zu denen ich auch die Mathematiker zähle) jederzeit vom Algorithmus des Lebens gesteuert, der dafür sorgt, dass die DNA transkribiert wird, die Zellen ihren Stoffwechsel aufrechterhalten, etc. Mathematik treiben, wie Spielen überhaupt,  muss man vielleicht als "Abfallprodukt" des algorithmisch gesteuerten Lebens auffassen, eine Form des Überflusses, der Freiheit, die einen das Programm des Lebens gewährt. Überleben geht zwar vor, aber dann bleibt noch viel Raum für algorithmische und nicht-algorithmische Spielchen.

  8. Steffen Rehm Antworten | Permalink

    Urknall

    AM ANFANG WAR DER ALGORITHMUS

  9. Dr. Webbaer Antworten | Permalink

    @Chrys

    Seit 1931 weiß man aufgrund der Arbeiten von Kurt Gödel, dass im Rahmen eines jeden (hinreichend reichhaltigen) formalen Systems Aussagen formulierbar sind, die man als wahr erkennen kann, die man aber nicht mit den Mitteln des Systems beweisen kann (siehe auch den Beitrag: "Innenwelt und Außenansicht").

    Diese zwei Fragen gingen auch:

    Wann oder warum genau werden in "hinreichend reichhaltigen" Systemen 'Aussagen [, die] formulierbar sind, die man als wahr erkennen kann mit den Mitteln des Systems' unbeweisbar? Worin genau besteht diese "hinreichende Reichhaltigkeit"?

    MFG
    Dr. Webbaer

  10. Chrys Antworten | Permalink

    @Dr. Webbaer / Ein Erklärungsversuch

    Es ist für Gödels Beweis seines Unvollständigkeitstheorems von Belang, dass sich mit den formalen Sprachmitteln eines Kalküls ein Statement formulieren lässt, welches interpretierbar ist als

    "Diese Aussage ist nicht beweisbar."

    Bezeichne ich diesen hervorgehobenen Ausdruck mit A, dann sind zwei Fälle zu unterscheiden:

    i) A ist beweisbar. Dann ist die Behauptung von A falsch. Somit ist der Kalkül nicht widerspruchsfrei, da er mit A eine falsche, aber beweisbare Aussage zulässt.

    ii) A ist nicht beweisbar. Dann ist die Behauptung von A wahr. Somit ist der Kalkül nicht vollständig, da er mit A eine wahre, aber unbeweisbare Aussage zulässt.

    Der Fall i) wird für das Theorem dadurch erledigt, dass die Widerspruchsfreiheit des Kalküls explizit vorausgesetzt wird. Die "hinreichende Reichhaltigkeit" ist dann eine Forderung an die syntaktischen Mittel eines Kalküls, nämlich dass diese eine zu A korrespondierende formale Aussage gestatten. Die eigentliche Mühsal von Gödels Beweis steckt in dem Nachweis, dass dies stets möglich ist, wenn mit den Mitteln des Kalküls die Peano Arithmetik formulierbar ist.

    Beim Entscheidungsproblem liegt die Sache etwas anders. So hatte Gödel ja die Vollständigkeit des engeren Funktionenkalküls (first-order logic) bewiesen. Alonzo Church hat dann 1936 aber gezeigt, dass in diesem Kalkül für einen gegebenen Ausdruck nicht mehr in endlich vielen Schritten entschieden werden kann, ob er wahr ist.

  11. Dr. Webbaer Antworten | Permalink

    @Chrys

    Der letzte Absatz Ihrer Nachricht wurde hier nicht verstanden, der andere Teil Ihrer Nachricht entspricht einem "Diese Aussage ist falsch", was in sich widersprüchlich wäre, wenn man rekursive Aussagen zulässt.

    Sicherlich ein weites Feld, grundsätzlich sind im hier bearbeiteten Sinne Systeme möglich, die keine der beschriebenen Probleme verursachen. - Irgendwie wird die Argumentation wohl darauf hinauslaufen, dass diese dann nicht hilfreich wären, schon verstanden.

    Der Gedanke, dass hier erörterte Axiomatiken wie beschrieben problematisch sein müssen, gefällt diesem Schreiber aber nicht. Oder er benötigte noch weitere Erläuterung oder gar Betreuung. :-)

    MFG
    Dr. Webbaer

  12. Chrys Antworten | Permalink

    @Dr. Webbaer / Vorsicht, Fallstrick!

    Attention: Wahrheit betrifft die Semantik, Beweisbarkeit aber die Syntax eines formalen Kalküls. Der Ausdruck, "Diese Aussage ist falsch", ist eine semantische Antinomie, im Unterschied zu "Diese Aussage ist unbeweisbar," was eine rekursive Feststellung zur Syntax ist.

    Gödels Theorem sagt also etwas aus über die Beziehung zwischen Syntax und Semantik eines widerspruchsfreien Kalküls. Ist die Syntax nur "hinreichend reichhaltig", so lassen sich in dem fraglichen Kalkül stets Aussagen formulieren, die semantisch wahr aber syntaktisch unbeweisbar sind.

    Beim Entscheidungsproblem geht es um die Möglichkeit der Beurteilung, ob eine Aussage wahr ist oder nicht. Das sagt zunächst nur etwas zur Semantik und nicht zur Syntax. -- Eigentlich wollte ich nur darauf hinweisen, dass dieses Problem mit dem der Vollständigkeit nicht verwechselt werden darf, aber vielleicht sind meine Worte da auch mehr verwirrend als erhellend.

  13. Dr. Webbaer Antworten | Permalink

    @Chrys

    Sie meinen dass die Wahrheit (ein Eigenschaftswert einer Aussage), die zu beweisen durch Rückführung einer Aussage auf ein Axiom gelingt, in syntaktisch ungeeigneten Systemen eben nicht gelingt, obwohl sie gelingen müsste - dem Anschein nach?

    Helfen Sie vielleicht noch ein wenig diesen Anschein betreffend.

  14. Josef Honerkamp Antworten | Permalink

    Hinweis auf Penrose-Buch:

    Ein Fundgrube für Überlegungen rund um den Gödelschen Satz ist das Buch von Roger Penrose: Schatten des Geistes - Wege zu einer neuen Physik des Bewusstseins, Spektrum Akademischer Verlag,1995. Man muss dabei ja seinen Wegen zur einer "neuen Physik" nicht unbedingt folgen.

  15. Chrys Antworten | Permalink

    @Dr. Webbaer

    Eine Aussage ist ja nicht per se oder irgendwie "an sich" wahr. Ein klassisches Beispiel dazu wäre Euklids Parallelenaxiom. Das wird erst dadurch wahr oder falsch, indem es als wahr oder falsch interpretiert wird, und in Abhängigkeit von einer solchen Interpretation gelangt man zu unterschiedlichen Modellen von Geometrie. Genauer gesagt, man spricht von einem Modell, wenn darin alle Theoreme eines Kalküls (Axiome und nach syntaktischen Schlussregeln abgeleitete Formeln) als wahr interpretiert werden. Die Semantik ist gerade der Bereich, der sich mit derlei Interpretationen befasst. Ohne die Semantik können wir überhaupt nicht von "wahren" oder "falschen" Aussagen reden, dies sind rein semantische Attribute.

    Von "syntaktisch ungeeigneten Systemen" würde ich keinesfalls reden. Es hat allenfalls "ungeeignete Interpretationen", nämlich solche, mit denen ein Kalkül nicht widerspruchsfrei ist (denn damit liesse sich keinerlei Erkenntnis gewinnen). Die Angelegenheit wird durch die Möglichkeit des Selbstbezugs doch überhaupt erst spannend, also wenn ein widerspruchsfreier Kalkül syntaktisch reichhaltig genug ist, um rekursive Aussagen des zuvor genannten Typs zu formulieren. Dass die Peano Arithmetik dann bereits bis an die Grenzen der formalen Beweisbarkeit führt -- well, that's not a bug, it's a feature!

  16. Dr. Webbaer Antworten | Permalink

    Gödelscher Satz

    Der Schreiber dieser Zeilen kann leider nicht, was bestimmte Konzepte der sozusagen real existierenden Mathematik betrifft, immer folgen und sein Unbehagen beim Gödelschen Unvollständigkeitssatz ist philosophischer Art, will auch an dieser Stelle nicht vertiefen und ... dankt stattdessen sehr für die Hinweise, die neben dem Thema "Berechnungsvorschriften" hier im Feedback-Bereich gekommen sind!

    MFG
    Dr. Webbaer

  17. Chrys Antworten | Permalink

    Gödel und AIT

    Ganz bemerkenswert ist sicherlich noch, dass die algorithmische Informationstheorie einen alternativen Zugang zu Gödels Theorem erlaubt. Dies eröffnet einen anderen Blickwinkel, und vielleicht ist die Sache auf diese Weise ja auch leichter zu verkraften: »In such an approach it is possible to argue that if a theorem contains more information than a given set of axioms, then it is impossible for the theorem to be derived from the axioms.«

    G. Chaitin. Gödel's Theorem and Information. Internat. J. Theoret. Phys., 21 (1982) 941-954 [HTML]

  18. Josef Honerkamp Antworten | Permalink

    @Chris

    Auch von mir vielen Dank für die erhellenden Kommentare.

  19. Chrys Antworten | Permalink

    @Josef Honerkamp

    Vielleicht etwas off-topic, aber da das Entstehen neuer Ideen und Konzepte durch menschliches Denken im jedem Falle zumindest unterschwellig mit hineinspielt, möchte ich gerne die Gelegenheit nutzen und noch einen Wunsch für ein vorstellbares Blogthema äussern. Gerade Ihre persönlichen Erfahrungen dürften bei der Leserschaft hier doch einiges Interesse finden, würde ich meinen.

    In einer Pressemitteilung des Clay Mathematics Institute vom 18. März 2010, betreffend die Millennium Prize Zuerkennung an Grigorij Perelman, wird eine Ihrer Publikationen gewürdigt als ein Beitrag zur Entdeckung des Ricci Flusses in der Physik [Link]. Etwas mehr zu den Hintergründen und Zusammenhängen dieser Arbeit quasi aus erster Hand zu erfahren, das könnte gewiss noch spannend sein, und wenn Sie das irgendwann einmal thematisch aufgreifen würden...

    Mir war bis zu dieser Pressemitteilung beispielsweise überhaupt nicht bekannt, dass der Ricci Fluss ganz unabhängig auch in der Physik gefunden wurde.

  20. Josef Honerkamp Antworten | Permalink

    @Chris

    Ich war einige Zeit verreist und habe dabei den Ricci-Fluss aus den Augen verloren. So will ich jetzt schnell nachschieben: Ich kenne den Ricci-Tensor aus der Allgemeinen Relativitätstheorie. Jeder, der sich mit dieser Theorie beschäftigt, lernt diesen sehr bald kennen.
    Über den Ricci-Fluss habe ich aber erst von Ihnen erfahren. So wie er definiert wird (http://de.wikipedia.org/wiki/Ricci-Fluss), ist er eine rein mathematische Konstruktion: Die definierende Gleichung ist nicht relativistisch kovariant, die Mannigfaltigkeit,deren Evolution damit beschrieben wird, kann nicht die Raumzeit sein.

  21. Chrys Antworten | Permalink

    @Josef Honerkamp

    Konkret war es die folgende Textstelle aus der CMI Pressemitteilung, die mich zum Fragen veranlasst hatte:

    [The Ricci flow equation] was discovered two times, independently. In physics, the equation originated with the thesis of Friedan [F, 1985], although it was perhaps implicit in the work of Honerkamp [Ho, 1972]. [...] The physicists were working on the renormalization group of quantum field theory, while Hamilton was interested in geometric applications of the Ricci flow equation itself.

    Die hier erwähnte Entdeckung des Ricci Flusses in der Physik war mir, wie gesagt, völlig neu, während die Rolle von Richard Hamilton in dieser Geschichte quasi zum mathematischen Folklorewissen gehört. Abgesehen von James Carlson, der offenbar diese Pressemitteilung verfasst hat, scheint so gut wie niemand die physikalische Motivierung zur Kenntnis genommen oder zumindest der Erwähnung würdig befunden zu haben. Irgendwie hatte ich angenommen, dass den Physikern die Zusammenhänge dabei wesentlich mehr geläufig sein müssten, aber wie es aussieht, haben Sie die Sache auch nicht gerade auf dem Radarschirm.

    Die genannte Thesis von Friedan ist übrigens als Publikation noch hier [PDF].

    Mir scheint das jedenfalls noch ein recht bemerkenswertes Beispiel dafür zu sein, wie zwei unabhängige und unterschiedlich gewählte Denkansätze schlussendlich auf dieselbe Struktur führen können, ohne dass die Gemeinsamkeit sogleich offenkundig wird.

  22. jmg Antworten | Permalink

    Im "Communique de presse" vom 18 März 2010 schreibt James Carlson vom Clay-Institute auf Seite 6 folgendes (die fehlenden Akzente bitte ich zu entschuldigen):
    "L'equation differentielle qui allait jouer un role-cle pour resoudre la conjecture de Poincare est l'equation du flot de Ricci. Elle a ete decouverte de facon independante par le physicien Honerkamp [Ho:"Chiral multiloops"(1972)] en 1972 et par le mathematicien Richard Hamilton [Ha2] en 1982.
    Honerkamp travaillait sur le groupe de renormalisation en theorie quantique des champs et Hamilton s'interessait aux applications geometriques de l'equation."
    LINK: www.claymath.org/poincare/presse_long.pdf

    Auf deutsch: Sie gelten als der Entdecker des Ricci Flusses. Sie haben ihn geschlagene zehn Jahre vor einem Mathematiker namens Richard Hamilton entdeckt. So wie die Wikinger Amerika vor Kolumbus entdeckt haben. Wobei Kolumbus dachte er wäre in Indien gelandet. Wie es aussieht sind sie einfach achtlos am Ricci Fluss vorbei geschlurft als sie auf den Quantenfeldern umher wanderten ohne zu wissen, was sie da gerade entdeckt haben.
    Irgendwie finden die Mathematiker den Ricci Fluss ganz toll, weil er ein grundlegender Baustein für die Lösung der Poincare Vermutung durch Perelman war. Perelman hat die Annahme des Preises in Höhe von einer Million Dollar mit einer bemerkenswerten Begründung bis heute verweigert:
    "Perelman, der seine Arbeit im Internet publizierte, zeigte bisher weder Interesse daran, seinen Beweis in einer Fachzeitschrift zu veröffentlichen, noch daran, den Preis für sich zu beanspruchen. Das Clay-Institut in Cambridge, Massachusetts, USA, sprach Perelman nach eingehenden Prüfungen am 18. März 2010 das Preisgeld für die erste Lösung eines der sieben Millenniums-Probleme zu. Dieser lehnte die Auszeichnung jedoch ab. Er begründete diese Entscheidung damit, dass der US-Amerikaner Richard Hamilton einen gleichwertigen Beitrag zur Lösung des Problems geleistet habe."
    LINK: http://de.wikipedia.org/wiki/Grigori_Jakowlewitsch_Perelman

    Vielleicht sollten sie Perelman bitten sich die Million doch endlich abzuholen und sie mit Ihnen und Hamilton zu teilen.

  23. Josef Honerkamp Antworten | Permalink

    @Chris & jmg

    Ich habe damals bei meiner Arbeit ein invariantes Renormierungsprogramm im Kopf gehabt, an eine Renormierungsgruppenmethode noch gar nicht gedacht und an einen Ricci-Fluss schon gar nicht. Das Programm bezieht sich darauf, den Termen in der Störungstheorie trotz Divergenzen einen Sinn zu geben, die Methode sucht nach einem Fixpunkt in einer Landschaft von invarianten Theorien. Natürlich spielt solch eine manifest kovariante Renormierungsmethode eine Rolle bei Berechnungen im Rahmen der Renormierungsgruppenmethode, wie Friedan 1985 in seiner Dissertation dann auch ausführt. Auf die Idee, einen Ricci-Fluss zu definieren, muss dann wohl ein Mathematiker kommen, der ganz andere Sichtweisen und Ziele hat.
    Übrigens: In meinem Buch "Statistical Physics" habe ich in Kap.2.6 eine Einführung in die Idee der Renormierungsgruppe (für Zufallsvariablen) gegeben, die mir diese Methode erst richtig nahe gebracht hat.

  24. MichiS Antworten | Permalink

    Sir Roger Penrose (SRP)

    Zitat:'Ein Fundgrube für Überlegungen rund um den Gödelschen Satz ist das Buch von Roger Penrose: Schatten des Geistes - Wege zu einer neuen Physik des Bewusstseins, Spektrum Akademischer Verlag,1995. Man muss dabei ja seinen Wegen zur einer "neuen Physik" nicht unbedingt folgen.'

    im seinem neuen ETH-Vortrag gibt es ab Minute 40' eine spannende Stelle zum GOEDEL-THEOREM, auch für uns NICHTikerInnen gut für die Ahnung des Problems (:-)):
    http://www.youtube.com/...bedded&v=M5XYf1GJBhg

    1. Wo ist der kritische Punkt...ab welcher Stelle (Minute, Sekunde) wirds aus ExpertInnensicht problematisch in Bezug auf die Diskurse um SRP und den Gödelschen Satz ?

    2. @Honerkamp: Ihr Standpunkt zu (...nicht unbedingt zustimmen.)interessiert mich sehr!!!! Könnten Sie sich dazu outen ?

    TIA + überhaupt VIELEN DANK !

  25. Josef Honerkamp Antworten | Permalink

    @MichiS

    Penrose ist Platoniker und seine Folgerungen aus den Gödelschen Überlegungen sind ganz davon beeinflusst. Ich glaube nicht, dass Konstruktionen unseres menschlichen Geistes eine eigene Existenz haben, sondern eben nur in unseren Köpfen vorhanden sind und als Information von Mensch zu Mensch übertragen werden, zum großen Teil über den Umweg von Strukturen in der materiellen Welt (Schrift, Bilder, elektronische Speichermedien, etc).

  26. Chrys Antworten | Permalink

    Understanding Penrose

    Roger Penrose hatte zu seinem Buch (Shadows of the Mind) diverse kritische Reaktionen erhalten, zu denen er dann auch eine Entgegnung verfasst hat; er fühlte sich da in verschiedener Hinsicht missverstanden. In gesmmelter Form lässt sich das hier finden (1.-10. der Liste):
    http://www.calculemus.org/...alis/NS/10/index.html

  27. Blickensdörfer Antworten | Permalink

    Eine gut begründete und doch leicht lesbare Erläuterung, was mit dem Wort „Algorithmus“ und als „algorithmische Verfahren“ zu verstehen ist. Ich hoffe das gelingt mir ebenso mit dem, was ich nachfolgend zu bedenken gebe.
    Mit der überlieferten Übersetzung des Wortes „Algorithmus“ ist auch das historische Verständnis dazu überliefert worden. Es sei Bezeichnung für ein überliefertes Verständnis von der „Kunst des Rechnens“, von der Art und Weise des Rechnens mit Zahlen, von Berechnungsverfahren. Die mit diesem Verfahren erzielten Ergebnisse entsprachen „vernünftigen Schlussfolgerungen“, entsprachen einem logischen Denken. Deshalb aber nur dann, wenn das Verfahren mit abstrakten Zeichen angewendet wird.
    Ist diese Voraussetzung gegeben, kann das Verfahren nicht nur für ein Rechnen mit Zahlen angewendet werden. Mit ihm kann allgemein „vernünftig geschlussfolgert“ werden. Wird nun (trotzdem) zum Beispiel mit „Berechnungsverfahren“ oder mit „Folge von Anweisungen“ die Bedeutung des Wortes „Algorithmus“ erklärt, dann wird es, ohne diese Erläuterung, als relativer also als scheinbarer Begriff verwendet. Dafür gibt es aber keine vernünftige Begründung. Es war ein Begriff für die „Kunst des Rechnens“. Und heute?
    Für das daraus entwickelte (vertiefte) abstraktere Begreifen der „Kunst des Rechnens“ kann „Berechnungsverfahren“ nicht mehr als Begriff verwendet werden. Die Sprachlogik wäre gestört, vernünftig könnte damit nicht geschlussfolgert werden. Das ist allerdings auch nicht mit „Folge von Anweisungen“ oder „Handlungsvorschrift zur Lösung eines Problems“ möglich. Feststellbar sind in Technik und Natur, zu der auch der Mensch gehört, Reihenfolgen (Abfolgen) von mit einander kausal und/ oder logisch verbundenen Ereignissen, und Reaktionen. Das Rechnen gehört dazu. Es sind zusammenhängende sich bedingende Abfolgen, ob sie der Mensch versteht oder nicht. Sie könnten als Algorithmus bezeichnet werden. „Algorithmus“ ist also auch kein Subjekt, das etwas „reicht“.
    Kennt der Mensch einen so verstandenen Algorithmus nicht, mit dem er etwas verändern, erhalten, verhindern oder erreichen will, dann – so der allgemeine Sprachgebrauch – hat er ein „Problem“. Mit dem Wort „Aufgabe“: die „Handlungsvorschrift“ (der Algorithmus) ihres Lösens ist bekannt, wird also etwas anderes als mit dem Wort „Problem“ verstanden. Diese Worte sind vernünftigerweise sprachlogisch nicht bedeutungsgleich zu verwenden. Ein Problem ist auch schon deshalb nicht als entscheidbar oder als nicht entscheidbar zu verstehen. „Entscheidbar ist ein gar zu menschliches Adjektiv. Entscheidbar versteht der derjenige, der zu etwas (Aus-)Wählbares entscheiden will, also auch dazu, nicht entscheiden zu wollen.
    Entscheidbar ist die Grammatik nicht. Sie ist eine „Handlungsvorschrift“ und kann als Algorithmus verstanden werden, mit dem Sprachlogik gewährleitet werden sollte. Die Voraussetzung dafür ist die Anwendung von Worten und Worteverbindungen als Begriffe, die nicht nur logisch wahr sind sondern auch nicht beliebig in Aussagen verstanden werden (können). Mit diesem „Begreifen“ beginnt Wissenschaft, auf solche Aussagen gründet (begründet) sich Wissenschaft. Wissenschaftlich ist nicht zu fragen. „Was ist ein Algorithmus?“. Die darunter gegebenen Erläuterungen bestätigen die Notwendigkeit der Beantwortung der Frage: Was ist mit dem Wort „Algorithmus“ (heute) zu begreifen, damit es als Begriff verwendet werden kann.
    Freilich: ein mit leichter Sprache begreifendes Denken ist selbst bedenkenswert.

Einen Kommentar schreiben


8 + drei =