Apa yang diperlukan untuk perhitungan analog universal?

Operasi apa yang perlu dilakukan untuk melakukan perhitungan analog sewenang-wenang ? Apakah penambahan, pengurangan, penggandaan, dan pembagian cukup?

Juga, apakah ada yang tahu persis masalah apa yang dapat ditelusuri menggunakan perhitungan analog, tetapi tidak dengan digital?

Sayangnya, tidak ada konsep universalitas dalam komputasi analog. Namun, makalah ini oleh Delvenne mengusulkan formalisme pemersatu untuk universalitas dalam sistem dinamik diskrit (misalnya Turing) dan kontinu (misalnya persamaan diferensial) dan ulasan beberapa sistem universal yang dipelajari dalam literatur. Berikut adalah kutipan dari makalah yang secara informal menjelaskan prosedur untuk membuktikan universalitas sistem dinamis:

Tetapi sebagian besar sistem dinamis yang dipelajari dalam matematika dan fisika memiliki ruang keadaan yang tak terhitung, misalnya automata seluler, persamaan diferensial, peta linear berurutan, dll. Contoh dari sistem tersebut telah terbukti universal. Masalah terputusnya mereka ditiru dari mesin Turing dengan cara berikut. Kami memilih keluarga tertentu dari negara bagian awal, dan keluarga negara bagian terakhir yang dapat dihitung, atau kelompok negara bagian terakhir. Kemudian masalah penghentian diberikan keadaan awal dan keadaan akhir / himpunan negara, apakah lintasan dimulai dari keadaan awal akan mencapai keadaan akhir / himpunan negara. Contoh yang lebih spesifik diberikan pada Bagian 7.

Jean-Charles Delvenne, Apa itu mesin komputasi universal ?, Matematika dan Komputasi Terapan, Volume 215, Edisi 4, 15 Oktober 2009, Halaman 1368-1374

Saya tidak berpikir pertanyaan itu dapat dijawab kecuali kita memiliki definisi tentang jenis komputasi yang sedang kita bicarakan.

Universalitas model mesin dengan kelas komputasi berarti bahwa setiap komputasi dalam kelas tersebut dapat dihitung oleh mesin. Kecuali jika Anda mendefinisikan kelas "perhitungan analog arbitrer", kami tidak dapat menjawab apa yang dimaksud universalitas dengan mereka.

Sekarang, fungsi yang telah Anda daftarkan hanya akan memberi Anda polinomial dan hasil bagi mereka yang merupakan kelas fungsi yang agak kecil, Anda bahkan tidak dapat menghitung fungsi sederhana seperti , ⌊ x ⌋ , $2^x$$\lfloor x \rfloor$ , ... menggunakannya.$\sqrt x$

Jika pertanyaan Anda adalah apakah ada sistem fisik yang dimulai dari keadaan awal akan mencapai keadaan lain dalam beberapa waktu dan jika itu selalu dapat dihitung, maka jawabannya tergantung pada jenis fisika apa yang kita bicarakan, dan apa artinya mengatur konfigurasi awal dan mengamati hasilnya, dll.

Jika kita hanya berbicara secara matematis tentang fisika klasik (kita dapat mengatur konfigurasi awal apa pun hingga presisi tak terhingga dan tanpa pertimbangan tentang hal-hal seperti energi yang diperlukan untuk mengatur konfigurasi dan mengamati hasilnya sama dari sudut pandang matematika) maka telah diketahui untuk waktu yang lama bahwa ada persamaan diferensial tentang fungsi yang dapat dikomputasi dan solusinya tidak dapat dihitung, lihat Marian B. Pour-El, dan J. Ian Richards, " Komputasi dalam Analisis dan Fisika ", 1989.

Kasus yang menarik adalah jika masalah n-body dapat dihitung (dan jika saya ingat dengan benar jawabannya tidak, setidaknya untuk ).$n>4$

Secara umum, jika kita hanya dapat memeriksa kesetaraan dua bilangan real yang memberikan fungsi yang bukan kontinyu tipikal tipologi informasi tentang bilangan real dan karenanya tidak dapat dihitung oleh mesin Turing karena fungsi apa pun (termasuk fungsi tipe yang lebih tinggi) bahwa mesin Turing dapat menghitung secara kontinyu (topologi informasi).

TL; DR: Jika dengan "komputer analog", maksud Anda adalah penganalisis diferensial , jawabannya adalah adders, unit konstan dan integrator. Bournez, Campagnolo, Graça dan Hainry telah menunjukkan pada tahun 2006 ( paywalled / free reprint ) bahwa model yang diidealkan memungkinkan untuk menghitung semua fungsi yang dapat dihitung dalam kerangka analisis yang dapat dihitung , dan model ini hanya membutuhkan 3 jenis unit ini.

Fungsi transendental

$\sin$$\exp$$\log$

Model komputasi analog

Sebagaimana ditekankan oleh yang lain, konsep "perhitungan universal" kurang jelas untuk komputer analog daripada komputer standar, di mana gagasan alami yang berbeda tentang komputasi dalam model komputasi yang berbeda ditemukan pada tahun 1930-an (lihat halaman Wikipedia tentang Church Turing Thesis untuk rinciannya ) .

Untuk mendefinisikan universalitas seperti itu, pertama-tama kita harus mendefinisikan model yang baik untuk perhitungan analog, dan itu adalah tugas yang sulit, karena model tersebut harus diidealkan dan cukup alami untuk menjadi berguna, tetapi idealisasinya seharusnya tidak memberikan kekuatan yang tidak realistis kepada model. Contoh dari idealisasi yang begitu baik adalah pita tak terbatas dari mesin Turing. Masalah dengan komputer analog datang dengan bilangan real yang memungkinkan untuk membuat hal-hal yang tidak masuk akal seperti mesin Zeno . Namun, beberapa model tersebut telah diusulkan dan digunakan dalam literatur (The GPAC adalah subjek utama dari jawaban ini, tapi saya mencoba untuk menjadi lengkap dalam daftar di bawah ini, tanpa hypercomputer ):

• yang General Purpose Analog Komputer (GPAC), didefinisikan oleh Claude E.Shannon pada tahun 1941 ( paywalled pdf ) untuk model analisis diferensial . Definisi GPAC baru-baru ini disempurnakan dan kekuatan komputasi telah direvisi ke atas;
• mesin Blum-Shub-Smale , yang bekerja pada waktu diskrit pada bilangan real. Ini terkait erat dengan model RAM nyata yang sering digunakan dalam geometri komputasi;
• $\mathbb R$
• Jaringan saraf ;
• Analisis yang dapat dihitung, yang melihat bilangan real yang dapat dihitung oleh mesin Turing.

Kekuatan model GPAC

$\Gamma$$\zeta$$y(t)=\Gamma(t)$, tampaknya sudah lama sekali bahwa komputer analog seperti itu tidak "universal", karena tidak dapat menghasilkan beberapa fungsi komputer yang masuk akal, yang digunakan oleh ahli matematika.

$f$$y(t)$$f(x)$$x$$\gamma$$\zeta$.

Bournez, Graça dan Pouly kemudian menunjukkan pada 2013 bahwa komputer analog ini dapat secara efisien mensimulasikan mesin Turing ( p.181 dari pdf besar ) dan, pada 2014, bahwa kelas kompleksitas P dan NP setara dalam model ini.

Apakah akan berguna untuk mengusulkan bahwa sistem analog universal dapat dimodelkan dengan jaring saraf yang tak terbatas yaitu. Nilai input / output sistem analog lainnya dapat direplikasi jaringan saraf yang cocok untuk operasi tertentu, dan operasi dapat dirantai sesuai kebutuhan?

Sementara saya merumuskan pemikiran ini sendiri, pencarian berikutnya telah menunjukkan proposal yang serupa:

Apa yang muncul adalah tesis seperti Gereja-Turing, diterapkan pada bidang komputasi analog, yang menampilkan model jaringan saraf menggantikan mesin Turing digital (lihat di sini ).

Bisa dibilang semua yang Anda butuhkan adalah operasi primitif untuk memindahkan nilai dari satu node ke yang lain. Manset yang bisa menjadi plus, minus dan bagi untuk mendapatkan rasio antara koneksi.

Sekarang untuk masalah yang sulit dipecahkan, lihatlah di mana jaringan saraf telah berhasil diterapkan, atau sedang dalam performa karena diimplementasikan pada komputer yang terpisah.

(dan minta maaf jika pandangan orang awam saya tentang topik ini sangat jelas)