Semak semula prinsip Turing dan rasai kuasa pembuktian melalui percanggahan

Algoritma telah tersebar di mana-mana, dan nampaknya untuk setiap masalah yang boleh dinyatakan dalam istilah matematik yang tepat, terdapat algoritma yang sepadan. Walau bagaimanapun, ini tidak berlaku. Malah, beberapa masalah yang kelihatan mudah tidak dapat diselesaikan oleh algoritma Alan Turing, seorang perintis dalam kalangan saintis komputer, pernah membuktikan masalah "tidak boleh dikira" ini dalam kertas hampir satu abad yang lalu model matematik pengiraan yang melancarkan sains komputer moden.

Turing menunjukkan hasil terobosan ini menggunakan strategi berlawanan dengan intuitif: dia menentukan masalah, masalah yang menolak semua percubaan untuk menyelesaikannya. "Sebagai contoh, jika saya bertanya kepada anda apa yang anda lakukan, tidak kira apa jawapan anda, saya akan berkata, 'Apa yang saya akan lakukan adalah berbeza daripada apa yang anda katakan,'" kata Rahul Ilango, pelajar siswazah di MIT yang belajar sains komputer teori. Kandungan yang ditulis semula: Turing menunjukkan hasil terobosan ini dengan strategi berlawanan dengan intuitif: dia mentakrifkan masalah yang menentang semua percubaan untuk menyelesaikannya. "Sebagai contoh, jika saya bertanya kepada anda apa yang anda lakukan, tidak kira apa jawapan anda, saya akan berkata, 'Apa yang saya akan lakukan adalah berbeza daripada apa yang anda katakan.'" kata Rahul Ilango, seorang pelajar siswazah yang mempelajari komputer teori. sains di MIT

Strategi Turing adalah berdasarkan kaedah matematik lama yang dikenali sebagai "bukti pepenjuru." Berikut adalah penjelasan ringkas tentang logik di sebalik pembuktiannya

Strings

Bukti pepenjuru datang daripada helah bijak untuk menyelesaikan masalah tentang rentetan, di mana setiap bit boleh mempunyai nilai 0 atau 1. Penerangan masalahnya ialah: Memandangkan senarai rentetan, semua rentetan dalam senarai adalah sama panjang, bagaimana anda boleh menjana rentetan baharu yang tiada dalam senarai?

Kandungan yang ditulis semula: Salah satu strategi yang paling mudah ialah mempertimbangkan setiap rentetan yang mungkin mengikut urutan. Katakan terdapat lima rentetan, setiap satu dengan lima bit. Mula-mula ulangi untuk menyemak sama ada 00000 wujud dalam senarai. Jika ia tidak wujud, masalah itu diselesaikan; jika ia wujud, pergi ke 00001 dan ulangi proses. Pendekatan ini mudah, tetapi perlahan untuk senarai panjang yang terhasil daripada rentetan panjang

Diagonal ternyata menjadi alternatif yang berdaya maju untuk membina rentetan yang tidak wujud secara berperingkat. Bermula dengan bit pertama rentetan pertama dalam senarai, terbalikkannya dan ini akan menjadi bit pertama rentetan baharu. Kemudian terbalikkan bit kedua rentetan kedua dan gunakannya sebagai bit kedua rentetan baharu, ulangi ini sehingga anda sampai ke penghujung senarai. Dengan membalikkan operasi bit, anda memastikan bahawa rentetan baharu berbeza daripada setiap rentetan dalam senarai asal dengan sekurang-kurangnya satu kedudukan. (Mereka juga membentuk pepenjuru dalam senarai rentetan, oleh itu nama diagonal proof.)

Bukti pepenjuru hanya memerlukan pemeriksaan satu bit daripada setiap rentetan dalam senarai secara bergilir-gilir, jadi biasanya Jauh lebih cepat daripada kaedah lain, tetapi kuasa sebenar adalah sejauh mana ia menangani masalah rentetan panjang yang tidak terhingga.

Saintis komputer teori Ryan Williams dari MIT berkata: "Walaupun rentetan dan senarai boleh menjadi tidak terhingga, kaedah penjurian masih berkesan

George Cantor adalah orang pertama yang mengeksploitasi seorang yang berkuasa, dia adalah pengasas bidang itu." daripada matematik teori set. Pada tahun 1873, dia menggunakan pepenjuru untuk menunjukkan bahawa beberapa nilai tak terhingga lebih besar daripada yang lain. 60 tahun kemudian, Turing menggunakan versi pembuktian pepenjuru ini kepada teori pengiraan

The Limitation of Algorithm

Untuk membuktikan bahawa terdapat kelas masalah matematik yang tidak dapat diselesaikan oleh mana-mana algoritma, Turing mencadangkan teori. Jenis masalah ini mempunyai input dan output yang jelas, tetapi tiada proses yang ditetapkan untuk menukar input kepada output. Turing tertumpu terutamanya pada masalah membuat keputusan dan berusaha untuk mengukuhkan tugas yang samar-samar ini dengan lebih baik. Dalam masalah keputusan, input boleh menjadi sebarang rentetan yang terdiri daripada 0 dan 1, dan output boleh sama ada 0 atau 1

Menentukan sama ada nombor adalah perdana (hanya boleh dibahagikan dengan 1 dan dirinya sendiri) ialah contoh masalah keputusan — —Memandangkan rentetan input yang mewakili nombor, output yang betul ialah 1 jika nombor itu adalah perdana dan 0 jika ia bukan perdana. Contoh lain ialah menyemak program komputer untuk ralat sintaks. Rentetan input mewakili kod program yang berbeza - semua program boleh diwakili dengan cara ini kerana itulah cara ia disimpan dan dilaksanakan pada komputer - peraturannya ialah jika kod itu mengandungi ralat sintaks, maka output 1, jika tidak, Kemudian keluaran 0.

Hanya jika algoritma menghasilkan output yang betul untuk setiap input yang mungkin, ia boleh dikatakan menyelesaikan masalah - jika ia gagal sekali pun, ia bukan algoritma umum untuk menyelesaikan masalah. Biasanya, seseorang menentukan masalah yang ingin diselesaikan dan kemudian cuba mencari algoritma untuk menyelesaikannya. Turing menghidupkan logik ini apabila mencari masalah yang tidak dapat diselesaikan - dia membayangkan senarai tak terhingga semua algoritma yang mungkin dan menggunakan penpenjurukan untuk membina teka-teki yang bertentangan dengan setiap algoritma dalam senarai.

Sila bayangkan soalan baharu yang terdiri daripada 20 soalan Daripada bermula daripada konsep tertentu, penjawab mengemukakan contoh ketidakpuasan hati untuk setiap soalan secara bergilir-gilir. Apabila permainan tamat, responden telah menerangkan cadangan yang sepenuhnya terdiri daripada soalan yang bertentangan

Proses bukti pepenjuru Turing adalah untuk membuktikan setiap algoritma dalam senarai algoritma yang tidak terhingga panjangnya tentang: "Bolehkah algoritma ini menyelesaikan masalah yang ingin kami buktikan sebagai tidak boleh dikira?", sama seperti pertandingan permainan. Williams berkata: "Kaedah ini mengubah masalah asal menjadi 'masalah yang tidak terhingga.'"

Untuk memenangi permainan, Turing perlu mereka bentuk masalah di mana jawapan yang diberikan oleh setiap algoritma adalah negatif. Ini bermakna mencari input khusus yang menjadikan algoritma pertama mengeluarkan jawapan yang salah, input lain yang membuat algoritma kedua gagal, dan seterusnya. Beliau mendapati bahawa input khas ini menggunakan kaedah yang serupa dengan yang digunakan oleh Kurt Gödel tidak lama dahulu apabila beliau menunjukkan bahawa pernyataan rujukan sendiri seperti "Proposisi ini tidak boleh dibuktikan" boleh menyebabkan masalah dalam asas kemahiran matematik.

Kunci di sini ialah setiap algoritma (atau program) boleh diwakili sebagai rentetan 0s dan 1s. Ini bermakna, sama seperti dalam contoh penyemak ralat, algoritma boleh mengambil sebagai input pengekodan algoritma lain. Pada dasarnya, algoritma juga boleh mengambil pengekodannya sendiri sebagai input.

Dengan cara ini, kita boleh mentakrifkan masalah yang tidak boleh dikira, sama seperti masalah yang disebut dalam bukti Turing: "Memandangkan rentetan input yang mewakili kod algoritma, apabila algoritma itu sendiri Diberi kod sebagai input, biarkan algoritma mengeluarkan 1 jika ia mengeluarkan 0, dan 0 sebaliknya "Setiap algoritma yang cuba menyelesaikan masalah ini akan menghasilkan output yang salah pada sekurang-kurangnya satu input, iaitu input yang sepadan dengan kodnya sendiri. . Ini bermakna bahawa masalah anomali ini tidak dapat diselesaikan oleh mana-mana algoritma Penggunaan tidak berakhir di sini. Pada tahun 1965, Juris Hartmanis dan Richard Stearns menyesuaikan hujah Turing untuk menunjukkan bahawa tidak semua masalah boleh dikira adalah sama—sesetengahnya sememangnya lebih sukar daripada yang lain. Keputusan ini melancarkan bidang teori kerumitan pengiraan, kajian tentang kesukaran masalah pengiraan.

Pembangunan teori kerumitan mendedahkan batasan bukti pepenjuru Turing. Pada tahun 1975, Baker, Gill, dan Solovy menunjukkan bahawa banyak masalah yang tidak dapat diselesaikan dalam teori kerumitan tidak dapat diselesaikan dengan penpenjuruan sahaja. Yang paling penting daripadanya ialah masalah P/NP yang terkenal, iaitu persoalan sama ada ketepatan penyelesaian boleh disahkan dalam masa polinomial dan sama ada ia boleh diselesaikan dalam masa polinomialDiagonal The had bukti garis adalah hasil langsung daripada tahap abstraksi yang tinggi yang menjadikannya begitu berkuasa. Bukti Turing tidak melibatkan sebarang masalah tidak boleh dikira yang mungkin timbul dalam amalan - sebaliknya, masalah cenderung abstrak. pepenjuru lain terbukti sama jauh dari dunia nyata, jadi mereka tidak dapat menyelesaikan masalah dunia nyata.

Williams berkata: "Bukti pepenjuru tidak langsung menyentuh masalah itu sendiri, sama seperti melakukan eksperimen dengan kotak sarung tangan

Penurunan bukti pepenjuru , menunjukkan." bahawa penyelesaian masalah P/NP akan menjadi satu perjalanan yang panjang. Walaupun hadnya, bukti pepenjuru kekal sebagai salah satu alat utama dalam senjata ahli teori kerumitan. Pada tahun 2011, Williams menggabungkannya dengan pelbagai teknik lain untuk menunjukkan bahawa model pengiraan terhad tidak mampu menyelesaikan beberapa masalah yang amat sukar—hasil yang menyelesaikan masalah yang meresahkan penyelidik selama 25 tahun. Walaupun ini jauh daripada menyelesaikan masalah P/NP, ia masih menunjukkan kemajuan yang ketara.

Jika anda ingin membuktikan sesuatu itu mustahil, jangan memandang rendah kuasa penafian

Pautan asal:

#🎜 🎜#

Kandungan yang perlu ditulis semula ialah: https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/

#🎜🎜 #

Atas ialah kandungan terperinci Semak semula prinsip Turing dan rasai kuasa pembuktian melalui percanggahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!