Inwiefern ist die Mandelbrot-Menge „berechenbar“?

18

Das Mandelbrot-Set ist eine wunderschöne Kreatur in der Mathematik.

Es gibt viele schöne Bilder dieses Sets, die mit hoher Präzision erstellt wurden, so dass dieses Set in gewissem Sinne "berechenbar" ist.

Was mich jedoch beunruhigt, ist die Tatsache, dass es nicht einmal rekursiv aufzählbar ist - einfach weil die Menge unzählbar ist. Dies könnte gelöst werden, indem eine Art endliche Darstellung der Punkte benötigt wird.

Obwohl wir sicher wissen, dass viele Punkte zum Set gehören und andere nicht, gibt es auch viele Punkte, deren Mitgliedschaft im Set wir nicht kennen. Alle Bilder, die wir bisher gesehen haben, enthalten möglicherweise viele Punkte, die "bis zu n Iterationen gebunden bleiben", aber diese Punkte gehören möglicherweise nicht zum Satz.

Für einen bestimmten Punkt mit einer endlichen Darstellung lautet das Problem "Gehört dieser Punkt zur Menge?" hat sich noch nicht als entscheidbar erwiesen, wenn ich recht habe.

In welchem ​​Sinne (nach welcher Definition) können wir nun sagen, dass die Mandelbrot-Menge "berechenbar" ist?

computability Erdmaschine
quelle
9
"Was mich jedoch beunruhigt, ist die Tatsache, dass es nicht einmal rekursiv aufzählbar ist - einfach, weil die Menge unzählbar ist." - Das sollte dich wahrscheinlich nicht beschäftigen. Immerhin sind Unmengen wirklich einfacher Punktmengen in unzählbar. Zum Beispiel . R2R2
user2357112 unterstützt Monica

Antworten:

13

Es gibt verschiedene Möglichkeiten zu definieren, was es bedeutet, dass der Mandelbrot-Satz berechenbar ist. Eine mögliche Definition ist das Blum-Shub-Smale-Modell. In diesem Modell wird die reelle Berechnung von einer Maschine modelliert, die einer RAM-Maschine ähnelt, deren Zugriff auf reelle Zahlen auf Grundrechenarten und Vergleiche beschränkt ist. Blum und Smale zeigten, dass die Mandelbrot-Menge in diesem Modell nicht berechenbar ist, obwohl ihr Komplement mithilfe des herkömmlichen Algorithmus, mit dem sie gezeichnet wurden, rekursiv aufgelistet werden kann.

Ein anderes Modell ist eine berechenbare Analyse , bei der die Mandelbrot-Menge wahrscheinlich berechenbar ist, wie Hertling gezeigt hat (abhängig von einer weit verbreiteten Vermutung, der Hyperbolizitätsvermutung). In diesem Modell bedeutet die Berechnung der Mandelbrot-Menge, dass mit jeder gewünschten Genauigkeit eine Annäherung an die Mandelbrot-Menge berechnet werden kann (für die genaue Definition siehe den Verweis zur berechenbaren Analyse).

Warum scheint der Computer dann in der Lage zu sein, den Mandelbrot-Satz zu zeichnen? Die Hauptschwierigkeit beim Zeigen, dass der herkömmliche Algorithmus funktioniert, besteht darin, dass es schwierig ist, im Voraus zu sagen, wie viele Iterationen ausgeführt werden müssen, bevor wir entscheiden, dass der Punkt zur Menge gehört. Hertling zeigt, dass es eine vernünftige Grenze gibt, wenn die weit verbreitete Hyperbolizitätsvermutung zutrifft. Vermutlich warten die Programme einfach lange genug; oder sie warten nicht lange genug, sondern bekommen nur einen kleinen Bruchteil der Punkte falsch.

Yuval Filmus
quelle
Ich habe mir beide Modelle angesehen, aber beide sind nicht gut genug für mich ... Da das Beste neben finite kompakt und das Mandelbrot-Set kompakt ist, sollte es meines Erachtens ein Modell geben, das behauptet, es sei "computable compact". irgendwie. Für Mengen wie kann man "lokal kompakt berechenbar" sagen. R
Earth Engine
10

Grundsätzlich ist die Mandelbrotmenge (soweit wir wissen) nicht berechenbar. Die Tatsache, dass Sie Bilder sehen, bedeutet nicht, dass diese berechenbar sind. Diese Bilder werden mit einer Näherung berechnet: Wenn der Prozess als Heuristik länger als ein festgelegter Schwellenwert ausgeführt wird, geht der Code davon aus, dass er niemals beendet wird. Diese Heuristik kann falsch sein, weshalb diese Bilder möglicherweise nicht 100% genau sind. Mit anderen Worten, diese Bilder sind kein Bild der Mandelbrot-Menge. Sie sind eine Annäherung an die Mandelbrotmenge.

DW
quelle
Die Tatsache, dass wir nur Näherungswerte berechnen, ist meines Erachtens nicht das Problem. Die Frage wäre eher, ob diese Annäherungen zu einem Grenzwert konvergieren, der für Mandelbrot festgelegt ist, wenn Sie die Rechenzeit erhöhen. Verstehe ich dich falsch?
Babou
1
@babou, warum sollte das das Problem sein? Ich kann Ihnen einen Algorithmus geben, der eine Annäherung an das Halting-Problem darstellt, dh er konvergiert im Grenzbereich zur richtigen Lösung des Halting-Problems - aber das reicht nicht aus, um das Halting-Problem als berechenbar zu betrachten. Ich glaube nicht, dass du mich missverstehst.
DW
Ich muss irgendwo verwirrt sein. Ich hatte den Eindruck, dass unendliche Objekte als berechenbar angesehen werden können, wenn sie die Grenze einer unendlichen Folge berechenbarer Objekte darstellen, mit einigen spezifischen Bedingungen, wie sich die Konvergenz mit der Grenze verhalten muss. Es scheint eine Lücke in meinem Verständnis zu geben.
Babou
@babou, OK. Ich bezweifle nicht dein Gedächtnis / Verständnis. Ich hatte nicht von dieser Vorstellung von Berechenbarkeit gehört, aber ich glaube dir.
DW
Erstens sollten Sie immer an meinem Gedächtnis / Verständnis zweifeln. Vieles, was hier diskutiert wird, liegt nicht in meinem (früheren) Fachgebiet. Eigentlich hängt mein Verständnis davon ab, wie wenig ich über berechenbare Realdaten lese, die ich als einheitlich mit der erforderlichen Präzision berechenbar verstehe. Dann gibt es mein älteres semantisches Verständnis von unendlichen Strukturen als Grenzen endlicher Strukturen in teilweise geordneten Mengen, obwohl ich nicht sicher bin, wie die beiden zusammenhängen.
Babou