Apakah interaksi lebih kuat daripada algoritma?

Aku pernah mendengar motto interaksi lebih kuat daripada algoritma dari Peter Wegner . Dasar dari ide ini adalah bahwa (klasik) Turing Machine tidak dapat menangani interaksi, yaitu, komunikasi (input / output) dengan dunia luar / lingkungan.

Bagaimana ini bisa begitu? Bagaimana bisa sesuatu yang lebih kuat daripada Turing Machine? Apa inti dari kisah ini? Mengapa itu tidak terkenal?

Mesin Turing dapat menangani interaksi dengan baik, menggunakan kaset oracle. Cara kerjanya adalah sebagai berikut: dari sudut pandang komputer yang menangani interaksi, input dari operator hanyalah urutan bit yang dikirim ke komputer dari waktu ke waktu. Kita semua tahu bahwa sysadmin yang malas dapat menulis sebuah skrip untuk mengirim input ke program ketika diminta, sehingga sysadmin tersebut dapat pergi lebih awal. Mesin interaksi tidak memiliki cara untuk mengetahui apakah benar-benar ada operator langsung di konsol, atau apakah input sedang disalurkan dari program lain.

Setelah semua masukan interaksi dipersiapkan terlebih dahulu adalah sama, dalam hal teoritis, sebagai memiliki semua masukan pada pita terpisah yang digunakan oleh mesin Turing oracle. Setiap kali komputer biasanya akan meminta interaksi dari operator, mesin bukannya membaca dari tape masukan. Jika hal membaca dari tape tampaknya tidak valid dalam beberapa cara, mesin Turing tidak persis apa mesin interaksi akan melakukan pada menerima masukan itu.

Saya akan menebak bahwa Wagner menyadari kemampuan untuk menggunakan kaset oracle untuk memasukkan kode, sehingga Anda harus mengambil komentarnya dengan sebutir garam, atau Anda harus bertanya apa yang dia berarti. Saya percaya bahwa orang-orang yang memikirkan interaksi pada umumnya mengkhawatirkan dua hal:

• Komputer "nyata" memang memiliki interaksi, tetapi algoritma seperti yang didefinisikan oleh Turing tidak. Kita dapat menyiasatinya dengan mengkodekan input pada kaset oracle, tetapi ini masih tidak cocok dengan cara komputer nyata beroperasi. Mungkin menyenangkan untuk mempelajari model-model komputasi yang lebih dekat dengan komputer nyata.

• algoritma berbasis Oracle tidak sering dipertimbangkan dalam sehari-hari komputasi karena komputer biasa tidak datang dengan ajaib "oracle" data pasokan. Tapi kita mungkin dapat benar-benar hanya menggunakan seseorang sebagai peramal. Jika orang tersebut memahami data yang sedang diminta, mereka bahkan mungkin dapat membantu algoritma bersama, sehingga meningkatkan kinerjanya. Dengan kata lain manusia mungkin dapat memberikan rekaman oracle berguna bukan hanya satu acak, dan dalam prinsip ini mungkin menyebabkan metode komputasi yang kuat lebih cepat atau lebih dibandingkan dengan yang berbasis non-oracle. Hal yang serupa terjadi dengan komputasi acak, setelah semua, di mana mesin diberikan urutan bit acak sebagai masukan tambahan.

Menghidupkan Mesin Model komputasi, dan tidak memiliki konsep interaksi. Dalam arti sebuah mesin yang didukung interaksi dengan sistem luar dapat melakukan hal-hal Machine Menghidupkan tidak bisa. Namun perhitungan dilakukan antara sedikit masukan dari sumber luar dapat jelas selalu dimodelkan oleh Turing Machine, sehingga bahkan "IO Machine" tidak dapat melakukan apapun dengan luar masukan bahwa Turing Machine tidak bisa melakukan.

Dalam beberapa hal mesin seperti itu mungkin dapat "memutuskan" masalah yang tidak dapat diputuskan oleh Turing Machines, tetapi hanya jika Anda membayangkan bahwa sistem yang berinteraksi dengannya memiliki kekuatan Mesin super-Turing dan dapat diandalkan (dalam beberapa hal; keandalan probabilitas akan cukup).

Bayangkan sebuah program untuk Mesin IO seperti: "untuk setiap masukan rekaman awal, mencetak isi tape, kemudian membaca simbol dari input luar; menerima jika simbol adalah 1 dan menolak sebaliknya". Program ini dapat memutuskan masalah apa pun . Tetapi hanya jika sistem luar dapat berinteraksi dengan mampu memutuskan masalah; bagi saya itu bukan cara yang sangat menarik untuk mengatakan bahwa Mesin IO mampu memutuskan masalah yang tidak dapat diputuskan oleh Turing Machines.

Saya pikir akan selalu memungkinkan untuk merepresentasikan perhitungan interaktif dengan membayangkan sebuah mesin yang mengambil input pada rekamannya sebagai pengkodean dari beberapa konfigurasi sebelumnya bersama dengan input luar, dan membuat mesin berhenti dengan rekamannya yang berisi pengkodean konfigurasi bersama-sama dengan output. Maka proses "menjalankan program" berulang kali menjalankan mesin Turing ini secara mekanis, dengan hanya "non-mekanis" bagian menjadi Namun input luar bersumber. Saya yakin Anda dapat membuktikan bahwa jika sistem seperti itu mendapatkan inputnya dengan memberikan outputnya ke Mesin Turing laindibentuk untuk beroperasi dengan cara yang sama, maka sistem gabungan memiliki kekuatan komputasi identik dengan Turing Machine tunggal. Saya menemukan bahwa argumen yang meyakinkan bahwa perhitungan interaktif tidak lebih kuat dari perhitungan non-interaktif, kecuali jika sistem yang berinteraksi dengan komputasi lebih kuat daripada Mesin Turing .

Namun, ada pengertian non-teoretis di mana interaktivitas dapat menambah kemampuan komputer untuk menyelesaikan masalah. Ada banyak hal yang dilakukan manusia dengan sangat akurat sehingga kita tidak tahu cara membuat komputer bekerja dengan sangat baik. Tetapi ada banyak juga banyak hal yang dilakukan manusia sebagai sampah sehingga kita dapat melakukan komputer. Menggabungkan kedua dapat menyebabkan proyek-proyek seperti reCAPTCHA , yang secara efektif otomatis digitalisasi buku-buku oleh pertanian keluar masalah mengenali kata-kata kepada manusia dalam kasus-kasus sulit. Sistem yang dihasilkan komputer + kerja manusia mencapai hasil yang saat ini tidak praktis untuk mencapai dengan baik perhitungan sendiri atau tenaga kerja manusia saja.

Baru-baru ini ACM mengadakan simposium Ubiquity ' What is Computation? 'Di mana Peter Wegner menerbitkan sebuah artikel yang mencerminkan pandangannya tentang komputasi Interaktif.

Berikut adalah dua kutipan dari artikel oleh Peter Wegner:

Salah satu konsep baru, yang hilang dari mesin Turing awal, adalah "Interactive Computing," yang mengakomodasi interaksi dengan lingkungan selama perhitungan.

Mesin interaksi dapat melakukan bentuk komputasi yang lebih kuat daripada mesin Turing, dan dapat melakukan jenis pemikiran yang diajukan oleh Turing karena interaksi meningkatkan kinerja mereka dibandingkan mesin Turing.

Namun, Fortnow, yang memiliki sebuah artikel di simposium yang sama, tampaknya tidak setuju dengan pandangan Wegner dan percaya bahwa komputasi interaktif tidak menawarkan kekuatan tambahan atas Mesin Turing.

Untuk menambah campuran, tampaknya kami masih berdebat dan mendefinisikan perhitungan. Moshe Vardi memiliki artikel, Apa Itu Algoritma ?, Komunikasi ACM, Vol. 55, No. 3, Maret 2012.

Vardi melaporkan dua definisi baru dari algoritma. Yang pertama diusulkan oleh Gurevich dan yang kedua oleh Moschovakis.

Gurevich berpendapat bahwa setiap algoritma dapat didefinisikan dalam istilah mesin keadaan abstrak.

Moschovakis, sebaliknya, berpendapat bahwa sebuah algoritma didefinisikan dalam hal recursor, yang merupakan deskripsi rekursif dibangun di atas operasi sewenang-wenang diambil sebagai primitif.

Saya tidak berpikir model dengan IO "lebih kuat" daripada mesin Turing, mereka hanya memodelkan hal yang berbeda.

Secara teori, Anda bisa melihat IO sebagai (berisik?) Oracle. Dengan oracle yang sempurna Anda bisa komputer fungsi Turing-uncomputable; tapi di mana untuk mendapatkan oracle dari? Manusia adalah satu-satunya pilihan "super-Turing" (jika ada) dan kita dikenal sangat tidak bisa diandalkan.

Sebuah kelas program yang sesuai dengan model ini adalah bukti interaktif assisstants (misalnya Isabelle / HOL , Coq ). Mereka berurusan dengan spasi bukti diputuskan tapi (bisa dibilang) setiap bukti dapat ditemukan (dan diperiksa) dengan input pengguna yang sesuai.

Periksa ini :) " Ide dan Model Perhitungan Turing " https://www.cs.montana.edu/~elser/turing%20papers/Turing%27s%20Ideas%20and%20Models%20of%20Computation.pdf