Dalam arti apakah Mandelbrot diatur "dapat dihitung"?

Set Mandelbrot adalah makhluk yang indah dalam Matematika.

Ada banyak gambar indah dari himpunan ini yang dibuat dengan presisi tinggi, jadi jelas himpunan ini "dapat dihitung" dalam beberapa hal.

Namun, yang membuat saya khawatir adalah kenyataan bahwa itu bahkan tidak terhitung secara berulang - hanya karena set tidak terhitung. Ini bisa diselesaikan dengan meminta semacam representasi terbatas dari poin-poin.

Selain itu, meskipun kita tahu pasti bahwa banyak poin milik set dan yang lainnya tidak, ada juga banyak poin yang keanggotaannya tidak kita ketahui. Semua gambar yang telah kita lihat sejauh ini mungkin mencakup banyak titik yang "hingga n iterasi tetap terikat," tetapi titik-titik itu mungkin sebenarnya bukan milik set.

Jadi, untuk titik tertentu dengan presentasi terbatas, masalah "Apakah titik ini milik set?" belum terbukti decidable, jika saya benar.

Sekarang, dalam arti apa (dengan definisi apa) kita dapat mengatakan bahwa set Mandelbrot "dapat dihitung"?

computability Mesin Tanah
sumber

"Namun, yang membuat saya khawatir adalah kenyataan bahwa itu bahkan tidak dapat dihitung secara rekursif - hanya karena set tidak terhitung." - yang mungkin seharusnya tidak menjadi perhatian Anda. Setelah semua, ton set benar-benar sederhana poin di

tidak terhitung.

, misalnya.

R^{2}

$\mathbb R^2$

R^{2}

$\mathbb R^2$

user2357112 mendukung Monica

Jawaban:

Ada beberapa cara untuk mendefinisikan apa artinya bagi set Mandelbrot untuk dapat dihitung. Salah satu definisi yang mungkin adalah model Blum-Shub-Smale. Dalam model ini, perhitungan nyata dimodelkan oleh mesin yang mirip dengan mesin RAM, yang aksesnya ke bilangan real dibatasi untuk aritmatika dasar dan perbandingan. Blum dan Smale menunjukkan bahwa himpunan Mandelbrot tidak dapat dihitung dalam model ini, meskipun komplemennya dapat dihitung secara rekursif menggunakan algoritma tradisional yang digunakan untuk menggambar mereka.

Model lain adalah analisis yang dapat dihitung , di mana himpunan Mandelbrot mungkin dapat dihitung, seperti yang ditunjukkan oleh Hertling (tergantung pada dugaan yang diyakini secara luas, dugaan hiperbolik). Dalam model ini, menghitung himpunan Mandelbrot berarti dapat menghitung pendekatan ke himpunan Mandelbrot, dalam akurasi yang diinginkan (untuk definisi yang tepat, lihat referensi tentang analisis yang dapat dihitung).

Jadi, mengapa komputer tampaknya bisa menggambar set Mandelbrot? Kesulitan utama dalam menunjukkan bahwa algoritma tradisional berfungsi adalah sulit untuk menentukan terlebih dahulu berapa banyak iterasi yang harus dijalankan sebelum kita memutuskan bahwa titik tersebut adalah milik set. Hertling menunjukkan bahwa jika dugaan hiperbolisitas yang diyakini secara luas berlaku, maka ada ikatan yang masuk akal. Agaknya, program hanya menunggu cukup lama; atau mereka tidak menunggu cukup lama, tetapi hanya mendapatkan sebagian kecil dari poin yang salah.

Yuval Filmus
sumber

R

$R$

Pada dasarnya, himpunan Mandelbrot tidak dapat dihitung (sejauh yang kita tahu). Fakta bahwa Anda melihat gambar tidak berarti itu dapat dihitung. Gambar-gambar tersebut dihitung dengan menggunakan pendekatan: jika proses berjalan lebih lama dari ambang batas yang ditetapkan, sebagai heuristik, kode mengasumsikan bahwa itu tidak akan pernah berakhir. Heuristik ini bisa salah, dan akibatnya gambar-gambar itu mungkin tidak 100% akurat. Dengan kata lain, gambar-gambar itu bukan gambar dari "set" Mandelbrot; mereka merupakan perkiraan untuk set Mandelbrot.

DW
sumber

Fakta bahwa kita hanya menghitung perkiraan bukanlah masalah, saya akan berpikir. Masalahnya akan lebih apakah aproksimasi ini konvergen ke batas yang ditetapkan Mandelbrot jika Anda menambah waktu perhitungan. Apakah saya salah paham dengan Anda?

babou

@ Baou, mengapa itu menjadi masalah? Saya dapat memberikan Anda sebuah algoritma yang merupakan perkiraan untuk masalah Hentikan, yaitu, ia menyatu dalam batas ke solusi yang tepat untuk masalah Henti - tetapi itu tidak cukup bahwa kami akan menganggap masalah Henti sebagai hal yang dapat dihitung. Saya tidak berpikir Anda salah paham.

Saya pasti bingung di suatu tempat. Saya mendapat kesan bahwa objek tak terbatas dapat dianggap dapat dihitung jika mereka adalah batas urutan tak terbatas dari objek yang dapat dihitung, dengan beberapa kondisi khusus tentang bagaimana konvergensi dengan batas harus berperilaku. Sepertinya ada lubang dalam pemahaman saya.

babou

@ Bob, OK. Saya tidak meragukan ingatan / pengertian Anda. Saya belum pernah mendengar gagasan komputabilitas, tapi saya percaya Anda.

Pertama, Anda harus selalu meragukan ingatan / pemahaman saya. Banyak dari apa yang dibahas di sini bukanlah bidang keahlian saya (sebelumnya). Sebenarnya pemahaman saya bergantung pada apa yang sedikit saya baca tentang komputer yang dapat dihitung, yang saya pahami sebagai komputer yang dapat digunakan dengan presisi yang diperlukan secara seragam. Lalu ada pemahaman semantik saya yang lebih lama tentang struktur tak terbatas sebagai batas struktur terbatas dalam set yang dipesan sebagian, meskipun saya tidak yakin bagaimana keduanya terhubung.

babou