Tesis Church-Turing Diperpanjang

Salah satu pertanyaan yang paling banyak dibahas di situs itu adalah Apa Artinya Membantah Tesis Gereja-Turing . Ini sebagian karena Dershowitz dan Gurevich menerbitkan bukti Tesis Gereja-Turing adalah Buletin Logika Simbolik pada tahun 2008. (Saya tidak akan membahasnya di sini, tetapi untuk tautan dan komentar yang luas, silakan lihat pertanyaan aslinya, atau - - promosi diri yang tidak tahu malu - entri blog yang saya tulis.)

Pertanyaan ini adalah tentang Tesis Diperpanjang Gereja-Turing, yang, sebagaimana dirumuskan oleh Ian Parberry, adalah:

Waktu pada semua model mesin "wajar" terkait dengan polinomial.

Terima kasih kepada Giorgio Marinelli, saya mengetahui bahwa salah satu penulis pendamping dari makalah sebelumnya, Dershowitz, dan seorang mahasiswa PhD-nya, Falkovich, telah menerbitkan bukti Tesis Church-Turing yang Diperluas, yang baru saja muncul di lokakarya Perkembangan Model Komputasi 2011 .

Saya baru saja mencetak kertas pagi ini, dan saya telah membukanya, tidak lebih. Para penulis mengklaim bahwa mesin Turing dapat mensimulasikan perangkat komputasi berurutan dengan paling banyak overhead polinomial. Komputasi kuantum dan komputasi paralel berskala besar secara eksplisit tidak tercakup. Pertanyaan saya berkaitan dengan pernyataan berikut di koran.

Kami telah menunjukkan - seperti yang telah diperkirakan dan diyakini secara luas - bahwa setiap implementasi yang efektif, terlepas dari struktur data apa yang digunakannya, dapat disimulasikan oleh mesin Turing, dengan paling banyak overhead polinomial dalam kompleksitas waktu.

Jadi, pertanyaan saya: apakah ini benar-benar "dipercaya secara luas," bahkan dalam kasus perhitungan sekuensial "benar" tanpa pengacakan? Bagaimana jika semuanya acak? Komputasi kuantum akan menjadi contoh tandingan, jika faktanya itu bisa dipakai, tetapi apakah ada kemungkinan "lebih lemah" dari kuantum yang akan menjadi contoh tandingan juga?

Kata-kata kasar persiapan

Saya harus memberi tahu Anda, saya tidak melihat bagaimana berbicara tentang "bukti" dari CT atau ECT menambah cahaya untuk diskusi ini. "Bukti" seperti itu cenderung sama baiknya dengan asumsi yang ada di atasnya --- dengan kata lain, seperti yang mereka maksudkan dengan kata-kata seperti "perhitungan" atau "perhitungan efisien". Jadi mengapa tidak segera melanjutkan ke diskusi tentang asumsi, dan membuang kata "bukti"?

Itu sudah jelas dengan CT asli, tetapi bahkan lebih jelas dengan ECT --- karena tidak hanya ECT "secara filosofis tidak dapat dibuktikan," tetapi hari ini secara luas diyakini salah! Bagi saya, komputasi kuantum adalah contoh tandingan yang besar dan mencolok yang seharusnya menjadi titik awal diskusi modern tentang ECT, bukan sesuatu yang didorong ke samping. Namun makalah oleh Dershowitz dan Falkovich bahkan tidak menyentuh QC sampai paragraf terakhir:

Hasil di atas tidak mencakup perhitungan paralel skala besar, seperti perhitungan kuantum, karena ia berpendapat bahwa ada batas tetap pada tingkat paralelisme, dengan jumlah istilah kritis yang ditetapkan oleh algoritma. Pertanyaan tentang kompleksitas model paralel yang relatif akan diajukan dalam waktu dekat.

Saya menemukan hal di atas sangat menyesatkan: QC bukan "model paralel" dalam arti konvensional. Dalam mekanika kuantum, tidak ada komunikasi langsung antara "proses paralel" --- hanya gangguan amplitudo --- tetapi juga mudah untuk menghasilkan jumlah eksponensial "proses paralel." (Memang, seseorang dapat menganggap setiap sistem fisik di alam semesta melakukan seperti yang kita bicarakan!) Dalam kasus apa pun, apa pun yang Anda pikirkan tentang interpretasi mekanika kuantum (atau bahkan kebenaran atau kepalsuannya), jelas bahwa ia membutuhkan pemisahan diskusi!

Sekarang, lanjutkan ke pertanyaan (menarik) Anda!

Tidak, saya tidak tahu adanya contoh tandingan meyakinkan untuk ECT selain komputasi kuantum. Dengan kata lain, jika mekanika kuantum salah (dengan cara yang masih membuat alam semesta lebih "digital" daripada "analog" pada skala Planck --- lihat di bawah), maka ECT seperti yang saya mengerti masih tidak akan "dapat dibuktikan" (karena masih akan bergantung pada fakta empiris tentang apa yang dapat dihitung secara efisien di dunia fisik), tetapi itu akan menjadi hipotesis kerja yang baik.

Pengacakan mungkin tidak menantang ECT karena dipahami secara konvensional, karena bukti kuat hari ini bahwa P = BPP. (Meskipun perhatikan bahwa, jika Anda tertarik pada pengaturan selain masalah keputusan bahasa --- misalnya, masalah relasional, pohon keputusan, atau kompleksitas komunikasi --- maka pengacakan terbukti dapat membuat perbedaan besar. Dan pengaturan tersebut sangat masuk akal yang ingin dibicarakan; mereka bukan yang biasanya ada dalam pikiran ketika mereka membahas ECT.)

Kelas "contoh tandingan" lainnya untuk ECT yang sering diangkat melibatkan komputasi analog atau "hiper". Pandangan saya sendiri adalah bahwa, berdasarkan pemahaman terbaik kami saat ini tentang fisika, komputasi analog dan hiperkomputasi tidak dapat menskalakan, dan alasan mengapa mereka tidak bisa, ironisnya, adalah mekanika kuantum! Secara khusus, sementara kita belum memiliki teori gravitasi quantum, apa yang diketahui saat ini menunjukkan bahwa ada hambatan mendasar untuk menjalankan lebih dari 10 ⁴³ langkah perhitungan per detik, atau menyelesaikan jarak yang lebih kecil dari sekitar 10 ^-33 cm.

Akhirnya, jika Anda ingin mengambil dari diskusi apa pun yang mungkin menjadi tantangan yang masuk akal atau menarik untuk ECT, dan hanya memungkinkan perhitungan serial, diskrit, deterministik, maka saya setuju dengan Dershowitz dan Falkovich yang dipegang ECT! :-) Tetapi bahkan di sana, sulit untuk membayangkan "bukti formal" meningkatkan kepercayaan diri saya pada pernyataan itu - masalah sebenarnya, sekali lagi, adalah apa yang kita ambil kata-kata seperti "serial", "diskrit", dan "deterministik" untuk jahat .

Adapun pertanyaan terakhir Anda:

Komputasi kuantum akan menjadi contoh tandingan, jika faktanya itu bisa dipakai, tetapi apakah ada kemungkinan "lebih lemah" dari kuantum yang akan menjadi contoh tandingan juga?

Saat ini, ada banyak contoh menarik dari sistem fisik yang tampaknya mampu mengimplementasikan beberapa komputasi kuantum, tetapi tidak semuanya (menghasilkan kelas kompleksitas yang mungkin merupakan perantara antara BPP dan BQP). Selain itu, banyak dari sistem ini mungkin lebih mudah direalisasikan daripada QC universal penuh. Lihat misalnya makalah ini oleh Bremner, Jozsa, dan Shepherd, atau yang ini oleh Arkhipov dan saya sendiri.

Jawaban ini dimaksudkan sebagai pelengkap jawaban Scott Aaronson (yang saya setujui bersama).

Dari perspektif teknik, sangat mengejutkan bahwa artikel Dershowitz / Falkovich menggunakan kata "acak" hanya dalam arti "memori akses acak", dan lebih lagi, artikel tersebut tidak menggunakan kata "sampel" (atau salah satu varian) sama sekali. Sebaliknya, fokus analisis Dershowitz / Falkovic secara eksklusif terbatas pada perhitungan fungsi numerik.

Keterbatasan ini sangat mencolok karena sebagian besar sumber daya komputasi STEM modern (saya akan berani mengatakan) tidak menghormati pembatasan fungsi numerik, tetapi lebih ditujukan untuk menghasilkan sampel dari distribusi (misalnya, dinamika molekul, aliran fluida turbulen, propagasi fraktur , sistem putaran bising baik klasik maupun kuantum, gelombang merambat melalui media acak, dll.).

Dengan demikian, jika "Tesis Diperpanjang Gereja-Turing" (ECT) adalah memiliki relevansi substansial dengan perhitungan STEM didefinisikan secara luas, mungkin pembatasan eksklusif untuk fungsi numerik harus diangkat, dan pernyataan ECT umum yang diberikan, yang mencakup pengambilan sampel perhitungan (dan validasi serta verifikasinya).

Apakah versi ECT yang digeneralisasi untuk sampel ini masih berada dalam lingkup TCS sebagaimana dipahami secara tradisional? Jawabannya tampaknya adalah "ya", sesuai dengan FAQ TCS Stack Exchange :

Kami merujuk Anda ke deskripsi ACM Kelompok Minat Khusus tentang Algoritma dan Teori Komputasi (SIGACT) ... TCS mencakup berbagai topik termasuk perhitungan probabilistik ... Pekerjaan di bidang ini [TCS] sering dibedakan dengan penekanannya pada matematika. teknik dan kekakuan.

$\text{ECTT}$$\{0,1,+,\times\}$$\text{ECTT}$, yang mengatakan bahwa predikat kewajaran ini dipenuhi oleh model-model yang memiliki terjemahan waktu polinomial ke mesin Turing. Sebagai sebuah aksioma, itu tidak dapat dipalsukan dalam arti teori kita dapat membantahnya, asalkan teori itu konsisten untuk memulainya, tetapi kesehatan teori kita dapat dipalsukan: mungkin ada model perhitungan yang masuk akal yang tidak terkait dengan Mesin Turing oleh terjemahan waktu polinomial. Mengizinkan bahwa penemuan hipotetis ini mungkin melibatkan perubahan dalam berpikir tentang apa yang masuk akal, itulah cara saya melihat sisi formal. Tampaknya sepele dalam retrospeksi tetapi saya pikir ini adalah poin penting untuk menggambarkan matematika dari yang lainnya.

$\text{ECTT}$$\text{BPP}$$\text{P}$$\text{ECTT}$$\text{P} \neq \text{BPP}$$\text{BPP}$$\text{ECTT}$$\text{P}$$\text{ECTT}$$\text{P} \neq \text{BQP}$$\text{ECTT}$$\text{ECTT}$$\text{BPP}$$\text{BQP}$$\text{P}$

Sebagai contoh, misalkan saya mengklaim telah membangun mesin yang memperhitungkan angka dan runtime-nya memenuhi batas polinom tertentu. Mesin ada di dalam kotak, Anda memasukkan nomor yang tertulis pada pita kertas, dan mencetak faktor-faktornya. Tidak ada keraguan bahwa itu bekerja, karena saya telah menggunakannya untuk memenangkan tantangan RSA, menyita mata uang digital, faktor sejumlah besar pilihan Anda, dll. Apa yang ada di dalam kotak? Apakah ini jenis komputer baru yang menakjubkan, atau apakah itu komputer biasa yang menjalankan beberapa jenis perangkat lunak baru yang menakjubkan?

$\text{ECTT}$$\text{ECTT}$

$\text{ECTT}$$\text{EXPTIME}$$\text{P}_\text{CTC} = \text{PSPACE}$$\text{ECTT}$$\text{P} \neq \text{PSPACE}$

$\text{P} \neq \text{NP}$$\text{ECTT}$$\text{P} \neq \text{P}_\text{CTC}$$\text{P} = \text{NP}$$\text{ECTT}$$\text{ECTT}$$\text{NP}$$\text{3SAT}$$\text{P}$

$\text{EXPTIME}$$\text{ECTT}$$\text{EXPTIME} \neq \text{P}$$\text{ECTT}$

$\text{ECTT}$$\text{P} = \text{BPP}$$\text{ECTT}$$\text{P} \neq \text{BQP}$

$\text{ECTT}$$\{\in\}$$\text{ECTT}$$\{\in\}$

$\text{ECTT}$