El País berichtet am 7. Mai über eine Arbeit spanischer Mathematiker, die (symbolisch) eine Turing-Maschine aus Wasser gebaut haben. (Die Überschrift „Cuatro matemáticos demuestran que era imposible predecir el destino de 29.000 patitos de goma en el mar“ bedeutet „Vier Mathematiker beweisen, dass es unmöglich war, dass Schicksal der Quietscheentchen im Meer vorherzusagen“, sie bezieht sich auf ein Schiffsunglück vom Januar 1992.)

Es geht um die am 11. Mai in den Proceedings of the National Academy of Sciences erschienene Arbeit Constructing Turing complete Euler flows in dimension 3. Dort wird erklärt, wie man Lösungen der Euler-Gleichungen für reibungsfreie Strömungen benutzen kann, um eine Turing-Maschine zu bauen.

Es geht freilich nicht um die praktische Produktion von Computern, sondern umgekehrt darum, die Unlösbarkeit gewisser Probleme mit Turing-Maschinen zu verwenden, um letztlich die Unlösbarkeit der Euler-Gleichungen oder sogar der Navier-Stokes-Gleichungen für viskose Strömungen zu beweisen. Also nur ein theoretisches mathematisches Konzept zum Beweis der Unlösbarkeit (Ausbildung von Singularitäten) gewisser Differentialgleichungen.

Es ist eine bekannte Frage, ob man mit hinreichend komplexen physikalischen Systemen stets Turing-Maschinen bekommen kann. Terence Tao hatte 2014 ein Programm entworfen, mit diesem Ansatz die Unlösbarkeit der Navier-Stokes-Gleichungen zu beweisen, einem der sieben Milleniumprobleme. Mit der Arbeit der spanischen Mathematiker hat man jetzt erstmals eine Turing-Maschine aus hydrodynamischen Prozessen, wenn auch bisher nur aus solchen ohne Viskosität, noch nicht aus den Navier-Stokes-Gleichungen.

Kommentare (14)

  1. #1 Joachim
    8. Juni 2021

    Sehe ich das richtig, dass es darum geht, was mit Computern überhaupt berechnet werden kann (was ja bekannt ist)?

    Das überträgt man dann auf die Unlösbarkeit der Euler-Gleichungen? Wie soll das gehen? Denn es ist mehr berechenbar als primitiv rekursive Funktionen.

    Vermutlich liegt mein “Denkfehler” hier irgendwo bei der “Ausbildung von Singularitäten”. Schon wieder eine dumme Frage?

  2. #2 Joachim
    8. Juni 2021

    Okay ich muss den Kommetar “zurrück” nehmen.

    Denn wenn die Quietscheentchen “equivalent” zu einem Computer sind und die Gleichungen equivalent zu den Quietscheentchen, na dann folgt die Unlösbarkeit der Gleichungen (weil … ein Computer das eben nicht lösen kann).

    Richtig so ungefähr? Wenn ja, dann finde ich das absolut bemerkenswert (…)

  3. #3 Jere
    8. Juni 2021

    Wow, den Ansatz für Navier-Stokes kannte ich nicht. Das ist ja mal super cool!

    @Joachim:
    Ja, so hatte ich das auch verstanden. Also in etwa:
    1) Es gibt gewisse Probleme, die kann eine Turingmaschine nicht lösen. (Check, das ist schon lange bewiesen)
    2) Ich zeige, dass ich aus bestimmten Lösungen der Gleichungen eine Turingmaschine bauen kann (das ist jetzt für einen einfachen Spezialfall gezeigt)
    3) Irgendwie würde daraus folgen, dass diese Turingmaschine die Probleme aus 1) lösen könnte (here be dragons, da kenne ich mich jetzt auch nicht aus)
    4) Widerspruch, also können die bestimmten Lösungen aus 2) nicht existieren.

    [Ich bin wirklich kein Experte für das Thema, also sehr dankbar für Anmerkungen und Korrekturen]

  4. #4 Richard
    9. Juni 2021

    @Jere: Ich bin ebenfalls kein Experte auf dem Gebiet und habe eben nur das Abstract des Artikels gelesen, aber da sprechen die Autoren von “proving the existence of Turing complete fluid flows on a three-dimensional geometric domain” – d.h. sie zeigen, dass es Lösungen der Gleichungen gibt, die genau dieselben Probleme berechnen können wie eine Turing-Maschine (das bedeutet “turing complete”).

  5. #5 Matthias
    SC, USA
    9. Juni 2021

    @Jere, ich bin ebenfalls komplett unbeschlagen auf dem Gebiet, verstehe aber trotzdem (oder gerade deswegen) Ihren Gedankengang fuer 3). Ihr 2) sagt ja nur, dass fuer bestimmte Loesungen so eine T-Maschine gebaut werden kann, das schliesst Ihren Punkt 1) ja aber nicht aus. Also denke ich, Ihre Punkte 1) und 2) koennen so stehen, aber 3) folgt nicht daraus. Nur so mein Senf dazugegeben, siehe oben (“unbeschlagen auf dem Gebiet”).

  6. #6 Matthias
    SC, USA
    9. Juni 2021

    “…verstehe … Ihren Gedankengang NICHT …”, wollte ich natuerlich sagen.

    • #8 Thilo
      9. Juni 2021

      Das Bild ist aus der Wikipedia.

  7. #9 Karl-Heinz
    Graz
    9. Juni 2021

    @Thilo
    Sorry wegen Werbung.
    Mich hat nur fasziniert für welche Dinge ein Bild herhalten muss.

  8. #10 Karl-Heinz
    Graz
    9. Juni 2021

    Ich frage mich, was ist wenn die Lösungen nicht brav sondern pathologisch sind.
    Ein Beispiel sin (1/x) ist in der Nähe von 0 nicht sehr brav.

    https://www.wolframalpha.com/input/?i=plot+sin+%281%2Fx%29

  9. #11 Jere
    9. Juni 2021

    @Matthias: Ja, genau darum geht es. Ich versuche ja auch nur grob zu verstehen, wie das Grundgerüst des geplanten Beweises aussieht, und stelle mir das ganz naiv so vor:

    1) und 2) schließen einander nicht aus, also brauche ich irgendein 3) (wie auch immer das aussieht), damit ich den geplaten Widerspruch 4) bekomme, mit dem ich die Nicht-Existenz gezeigt habe.

    Es kann auch sein, dass es ein bisschen anders aussieht, und 2) sagt: “Für jede(?) Lösung bekomme ich eine Turingmaschine”, und 3) ist “Wenn diese Lösung bestimmte Regularitätseigenschaften hat, DANN folgt daraus, dass man damit Probleme berechnen kann, die für eine Turingmaschine unentscheidbar sind”.

  10. #12 Joachim
    9. Juni 2021

    @Karl-Heinz #10
    Ich nehme einmal an, dass sich die Lösungen auf das Bild beziehen und nicht auf “die Unlösbarkeit (Ausbildung von Singularitäten) gewisser Differentialgleichungen”?

    Oder doch? Gibt es darüber hinaus einen speziellen Grund (abseits der “falschen” Darstellung von wolframalpha) sin(1/x) zu verwenden? Wie wäre es mit z.B. sinc?

    Das sind Fragen und keine Kritik oder Wertung (man muss ja vorsichtig sein heute!)

  11. #13 Karl-Heinz
    Graz
    10. Juni 2021

    @Joachim

    Was meinst du mit mit falscher Darstellung von sin (1/x)?

  12. #14 Joachim
    10. Juni 2021

    Der Graph ist so nicht darstellbar, also falsch (Anmerkung in gnuplot, wolframalpha widerspricht meinen Browsereinstellungen ohne js)

    Aber mir ist klar geworden, dass dieses Beispiel sehr gut gewählt war (weit besser als sinc). Nur eigentlich ist ja klar, das sie “verrückt” spielt.

    Worauf wolltest du hinaus, damit ich nicht mehr spekulieren muss? (So oder so, interessant ist das sowieso).

    Und gibt es eine Originalquelle bzw. Formel für das Bild? Wikipedia ist groß…