W jakim sensie zestaw Mandelbrota jest „obliczalny”?

Zestaw Mandelbrota to piękne stworzenie w matematyce.

Istnieje wiele pięknych obrazów tego zestawu stworzonych z dużą precyzją, więc oczywiście ten zestaw jest w pewnym sensie „obliczalny”.

Jednak niepokoi mnie fakt, że nie można go nawet wyliczyć rekurencyjnie - po prostu dlatego, że zbiór jest niepoliczalny. Można to rozwiązać, wymagając pewnego rodzaju skończonej reprezentacji punktów.

Co więcej, chociaż wiemy na pewno, że wiele punktów należy do zestawu, a inne nie, istnieje również wiele punktów, których członkostwa w zestawie nie wiemy. Wszystkie obrazy, które widzieliśmy do tej pory, mogą zawierać wiele punktów, które „do n iteracji są ograniczone”, ale te punkty mogą w rzeczywistości nie należeć do zestawu.

Zatem dla danego punktu ze skończoną prezentacją problem „Czy ten punkt należy do zbioru?” jeśli nie mam racji, nie zostało jeszcze udowodnione, że jest rozstrzygalne.

W jakim sensie (według jakiej definicji) możemy powiedzieć, że zestaw Mandelbrota jest „obliczalny”?

computability

— Earth Engine
źródło

„Jednak niepokoi mnie fakt, że nie można go nawet wyliczyć rekurencyjnie - po prostu dlatego, że zbiór jest niepoliczalny”. - to prawdopodobnie nie powinno cię dotyczyć. W końcu mnóstwo naprawdę prostych zestawów punktów w jest niepoliczalnych. .

R^{2}

$\mathbb R^2$

R^{2}

$\mathbb R^2$

— user2357112 obsługuje Monikę

Odpowiedzi:

Istnieje kilka sposobów zdefiniowania, co to znaczy, że zestaw Mandelbrota ma być obliczalny. Jedną z możliwych definicji jest model Blum – Shub – Smale. W tym modelu obliczenia rzeczywiste modelowane są przez maszynę podobną do maszyny RAM, której dostęp do liczb rzeczywistych jest ograniczony do podstawowej arytmetyki i porównań. Blum i Smale pokazali, że zestaw Mandelbrota jest w tym modelu nieobliczalny, chociaż jego uzupełnienie można rekurencyjnie wyliczyć przy użyciu tradycyjnego algorytmu stosowanego do ich rysowania.

Innym modelem jest analiza obliczeniowa , w której zestaw Mandelbrota jest prawdopodobnie obliczalny, jak pokazano przez Hertlinga (uwarunkowany powszechnie przypuszczalną hipotezą hiperboliczną). W tym modelu obliczenie zbioru Mandelbrota oznacza możliwość obliczenia aproksymacji do zbioru Mandelbrota, z dowolną pożądaną dokładnością (dokładna definicja - patrz odniesienie na temat analizy obliczeniowej).

Dlaczego więc komputer wydaje się być w stanie narysować zestaw Mandelbrota? Główną trudnością w wykazaniu, że tradycyjny algorytm działa, jest trudność z góry powiedzieć, ile iteracji ma zostać uruchomionych, zanim zdecydujemy, że punkt należy do zbioru. Hertling pokazuje, że jeśli powszechnie uważa się hipotezę hiperboliczności, istnieje uzasadnione takie ograniczenie. Przypuszczalnie programy po prostu czekają wystarczająco długo; lub nie czekają wystarczająco długo, ale źle rozumieją tylko niewielką część punktów.

— Yuval Filmus
źródło

Spojrzałem na oba modele, ale oba nie są dla mnie wystarczająco dobre ... Ponieważ najlepszą rzeczą obok skończonego jest kompaktowy, a zestaw Mandelbrota jest kompaktowy, myślę, że powinien istnieć model, który twierdzi, że jest „kompaktowy obliczalny” jakoś. W przypadku zestawów takich jak

możemy powiedzieć „lokalnie kompaktowy obliczalny”.

R

$R$

— Earth Engine

Zasadniczo zestaw Mandelbrota nie jest obliczalny (o ile wiemy). Fakt, że widzisz obrazy, nie oznacza, że można je obliczyć. Te obrazy obliczają przy użyciu aproksymacji: jeśli proces działa dłużej niż ustawiony próg, jako heurystyka, kod zakłada, że nigdy się nie zakończy. Ta heurystyka może być błędna, w wyniku czego obrazy te mogą nie być w 100% dokładne. Innymi słowy, te obrazy nie są obrazem „zestawu” Mandelbrota; są one zbliżone do zestawu Mandelbrota.

— DW
źródło

Myślę, że fakt, że obliczamy tylko przybliżenia, nie jest problemem. Problemem byłoby raczej to, czy przybliżenia te zbiegną się do pewnego limitu, jakim jest zestaw Mandelbrota, jeśli zwiększysz czas obliczeń. Czy źle cię rozumiem?

— babou

@babou, dlaczego miałby to być problem? Mogę dać ci algorytm, który jest przybliżeniem problemu Haltinga, tj. Zbiega się w granicach do prawidłowego rozwiązania problemu Haltinga - ale to nie wystarczy, że uznamy problem Haltinga za obliczalny. Nie sądzę, że mnie źle zrozumiałeś.

— DW

Muszę się gdzieś pomylić. Miałem wrażenie, że obiekty nieskończone można uznać za obliczalne, jeśli są granicą nieskończonej sekwencji obiektów obliczalnych, z pewnymi szczególnymi warunkami zachowania konwergencji do tego ograniczenia. W moim rozumieniu wydaje się, że jest dziura.

— babou

@babou, OK. Nie wątpię w twoją pamięć / zrozumienie. Nie słyszałem o tym znaczeniu obliczalności, ale wierzę ci.

— DW

Po pierwsze, zawsze powinieneś wątpić w moją pamięć / zrozumienie. Wiele z omawianych tutaj zagadnień nie należy do mojej (dawnej) wiedzy specjalistycznej. W rzeczywistości moje rozumowanie opiera się na tym, co niewiele przeczytałem o obliczeniach rzeczywistych, które rozumiałem jako obliczalne z dowolną wymaganą precyzją w jednolity sposób. Potem jest moje starsze semantyczne rozumienie struktur nieskończonych jako granic struktur skończonych w częściowo uporządkowanych zbiorach, chociaż nie jestem pewien, w jaki sposób są one połączone.

— babou