Tesis Church-Turing merujuk kepada konsep kaedah yang cekap, sistematik, atau mekanikal dalam logik, matematik, dan sains komputer. Ia dirumuskan sebagai penerangan konsep intuitif kebolehkiraan dan, berhubung dengan fungsi rekursif am, lebih kerap dipanggil tesis Gereja. Ia juga merujuk kepada teori fungsi komputer yang boleh dikira. Tesis ini muncul pada tahun 1930-an, apabila komputer itu sendiri belum wujud. Ia kemudiannya dinamakan sempena Gereja Alonso ahli matematik Amerika dan rakan sekerjanya dari Britain, Alan Turing.
Kecekapan kaedah untuk mencapai hasil
Peranti pertama yang menyerupai komputer moden ialah Bombie, sebuah mesin yang dicipta oleh ahli matematik Inggeris Alan Turing. Ia digunakan untuk menguraikan mesej Jerman semasa Perang Dunia II. Tetapi untuk tesis dan pemformalan konsep algoritma, dia menggunakan mesin abstrak, yang kemudiannya dipanggil mesin Turing. Tesis membentangkanminat untuk kedua-dua ahli matematik dan pengaturcara, kerana idea ini memberi inspirasi kepada pencipta komputer pertama.
Dalam teori kebolehkiraan, tesis Church-Turing juga dikenali sebagai tekaan tentang sifat fungsi boleh dikira. Ia menyatakan bahawa untuk sebarang fungsi yang boleh dikira secara algoritma pada nombor asli, terdapat mesin Turing yang mampu mengiranya. Atau, dengan kata lain, terdapat algoritma yang sesuai untuknya. Contoh yang terkenal tentang keberkesanan kaedah ini ialah ujian jadual kebenaran untuk menguji tautologi.
Cara untuk mencapai sebarang hasil yang diingini dipanggil "berkesan", "sistematik" atau "mekanikal" jika:
- Kaedah ini ditentukan dari segi bilangan arahan tepat yang terhad, setiap arahan dinyatakan menggunakan bilangan aksara yang terhad.
- Ia akan berjalan tanpa ralat, akan menghasilkan hasil yang diingini dalam beberapa langkah tertentu.
- Kaedah ini boleh dilakukan oleh manusia tanpa bantuan dengan sebarang peralatan selain kertas dan pensel
- Ia tidak memerlukan pemahaman, gerak hati atau kepintaran orang yang melakukan tindakan
Terdahulu dalam matematik, istilah tidak formal "boleh dikira secara berkesan" digunakan untuk merujuk kepada fungsi yang boleh dikira dengan pensel dan kertas. Tetapi tanggapan tentang kebolehkiraan algoritma adalah lebih intuitif daripada apa-apa yang konkrit. Kini ia dicirikan oleh fungsi dengan hujah semula jadi, yang mana terdapat algoritma pengiraan. Salah satu pencapaian Alan Turing ialahperwakilan predikat tepat secara rasmi, dengan bantuan yang mungkin untuk menggantikan yang tidak formal, jika keadaan kecekapan kaedah digunakan. Gereja membuat penemuan yang sama.
Konsep asas fungsi rekursif
Perubahan predikat Turing, pada pandangan pertama, kelihatan berbeza daripada yang dicadangkan oleh rakan sekerjanya. Tetapi akibatnya, mereka ternyata setara, dalam erti kata bahawa setiap daripada mereka memilih set fungsi matematik yang sama. Tesis Church-Turing ialah penegasan bahawa set ini mengandungi setiap fungsi yang nilainya boleh diperolehi dengan kaedah yang memenuhi syarat kecekapan. Terdapat satu lagi perbezaan antara kedua-dua penemuan itu. Gereja hanya mempertimbangkan contoh integer positif, manakala Turing menyifatkan kerjanya meliputi fungsi boleh dikira dengan pembolehubah kamiran atau nyata.
Fungsi rekursif biasa
Rumusan asal Gereja menyatakan bahawa pengiraan boleh dilakukan menggunakan λ-calculus. Ini bersamaan dengan menggunakan fungsi rekursif generik. Tesis Church-Turing merangkumi lebih banyak jenis pengiraan daripada yang difikirkan pada asalnya. Contohnya, berkaitan dengan automata selular, penggabung, mesin pendaftaran dan sistem penggantian. Pada tahun 1933, ahli matematik Kurt Gödel dan Jacques Herbrand mencipta definisi formal bagi kelas yang dipanggil fungsi rekursif am. Ia menggunakan fungsi di mana lebih daripada satu hujah boleh dilakukan.
Membuat kaedahλ-calculus
Pada tahun 1936, Gereja Alonso mencipta kaedah penentuan yang dipanggil λ-calculus. Dia dikaitkan dengan nombor semula jadi. Dalam λ-calculus, saintis menentukan pengekodan mereka. Akibatnya, mereka dipanggil nombor Gereja. Fungsi berdasarkan nombor asli dipanggil λ-computable. Terdapat definisi lain. Fungsi daripada tesis Gereja dipanggil λ-computable di bawah dua keadaan. Yang pertama berbunyi seperti ini: jika ia dikira berdasarkan unsur Gereja, dan syarat kedua ialah kemungkinan diwakili oleh ahli λ-calculus.
Juga pada tahun 1936, sebelum mengkaji kerja rakan sekerjanya, Turing mencipta model teori untuk mesin abstrak yang kini dinamakan sempena namanya. Mereka boleh melakukan pengiraan dengan memanipulasi aksara pada pita. Ini juga terpakai kepada aktiviti matematik lain yang terdapat dalam sains komputer teori, seperti pengkomputeran probabilistik kuantum. Fungsi daripada tesis Gereja hanya kemudiannya dibuktikan menggunakan mesin Turing. Pada mulanya, mereka bergantung pada λ-calculus.
Kebolehkiraan fungsi
Apabila nombor asli dikodkan dengan sewajarnya sebagai jujukan aksara, fungsi pada nombor asli dikatakan boleh dikira Turing jika mesin abstrak menemui algoritma yang diperlukan dan mencetak fungsi ini pada pita. Peranti sedemikian, yang tidak wujud pada tahun 1930-an, akan dianggap sebagai komputer pada masa hadapan. Mesin Turing abstrak dan tesis Gereja menandakan era pembangunanperanti pengkomputeran. Telah terbukti bahawa kelas fungsi yang ditakrifkan secara rasmi oleh kedua-dua saintis bertepatan. Oleh itu, akibatnya, kedua-dua pernyataan digabungkan menjadi satu. Fungsi pengiraan dan tesis Gereja juga mempunyai pengaruh yang kuat terhadap konsep kebolehkiraan. Ia juga menjadi alat penting untuk logik matematik dan teori pembuktian.
Kewajaran dan masalah kaedah
Terdapat pandangan yang bercanggah tentang tesis. Banyak bukti telah dikumpulkan untuk "hipotesis kerja" yang dicadangkan oleh Church dan Turing pada tahun 1936. Tetapi semua kaedah atau operasi yang diketahui untuk menemui fungsi baru yang boleh dikira secara berkesan daripada yang diberikan telah disambungkan dengan kaedah membina mesin, yang tidak wujud ketika itu. Untuk membuktikan tesis Church-Turing, seseorang bermula daripada fakta bahawa setiap model pengiraan yang realistik adalah setara.
Disebabkan kepelbagaian analisis yang berbeza, ini biasanya dianggap sebagai bukti yang kukuh. Semua percubaan untuk mentakrifkan dengan lebih tepat tanggapan intuitif bagi fungsi yang boleh dikira secara berkesan ternyata setara. Setiap analisis yang telah dicadangkan telah terbukti untuk memilih kelas fungsi yang sama, iaitu yang boleh dikira oleh mesin Turing. Tetapi beberapa model pengiraan ternyata lebih cekap dari segi masa dan penggunaan memori untuk tugasan yang berbeza. Kemudian diperhatikan bahawa konsep asas fungsi rekursif dan tesis Gereja agak hipotesis.
Tesis M
Adalah penting untuk membezakan antara tesis Turing dan penegasan bahawa apa-apa yang boleh dikira oleh peranti pengkomputeran boleh dikira oleh mesinnya. Pilihan kedua mempunyai definisi tersendiri. Gandhi memanggil ayat kedua "Tesis M". Ia berlaku seperti ini: "Apa sahaja yang boleh dikira oleh peranti boleh dikira oleh mesin Turing." Dalam erti kata sempit tesis, ia adalah proposisi empirikal yang nilai kebenarannya tidak diketahui. Tesis Turing dan "Tesis M" kadang-kadang keliru. Versi kedua secara amnya tidak betul. Pelbagai mesin bersyarat telah diterangkan yang boleh mengira fungsi yang tidak boleh dikira Turing. Adalah penting untuk ambil perhatian bahawa tesis pertama tidak melibatkan yang kedua, tetapi konsisten dengan kepalsuannya.
Implikasi terbalik tesis
Dalam teori kebolehkiraan, tesis Gereja digunakan sebagai penerangan tentang pengertian kebolehkiraan oleh kelas fungsi rekursif umum. Orang Amerika Stephen Kleene memberikan rumusan yang lebih umum. Dia memanggil sebahagian rekursif semua fungsi separa boleh dikira oleh algoritma.
Implikasi terbalik biasanya dirujuk sebagai tesis terbalik Gereja. Ia terletak pada hakikat bahawa setiap fungsi rekursif bagi integer positif dinilai dengan cekap. Dalam erti kata yang sempit, tesis hanya menunjukkan kemungkinan sedemikian. Dan dalam erti kata yang lebih luas, ia merumuskan daripada persoalan sama ada mesin bersyarat ini boleh wujud di dalamnya.
Komputer kuantum
Konsep fungsi boleh dikira dan tesis Gereja menjadi penemuan penting untuk matematik, teori mesin dan banyak lagi sains lain. Tetapi teknologi telah banyak berubah dan terus bertambah baik. Diandaikan bahawa komputer kuantum boleh melakukan banyak tugas biasa dengan masa yang lebih singkat daripada yang moden. Tetapi persoalan tetap ada, seperti masalah berhenti. Komputer kuantum tidak dapat menjawabnya. Dan, menurut tesis Church-Turing, tiada peranti pengkomputeran lain juga.
