Tesis Church-Turing mengacu pada konsep metode yang efisien, sistematis, atau mekanis dalam logika, matematika, dan ilmu komputer. Ini dirumuskan sebagai deskripsi konsep intuitif komputabilitas dan, dalam kaitannya dengan fungsi rekursif umum, lebih sering disebut tesis Gereja. Hal ini juga mengacu pada teori fungsi komputer-komputasi. Tesis muncul pada 1930-an, ketika komputer itu sendiri belum ada. Itu kemudian dinamai setelah ahli matematika Amerika Gereja Alonso dan rekan Inggrisnya Alan Turing.
Efisiensi metode untuk mencapai hasil
Perangkat pertama yang menyerupai komputer modern adalah Bombie, mesin yang dibuat oleh matematikawan Inggris Alan Turing. Itu digunakan untuk menguraikan pesan Jerman selama Perang Dunia II. Tetapi untuk tesis dan formalisasi konsep algoritma, ia menggunakan mesin abstrak, yang kemudian disebut mesin Turing. tesis menyajikanmenarik bagi matematikawan dan programmer, karena ide ini mengilhami pencipta komputer pertama.
Dalam teori komputabilitas, tesis Church-Turing juga dikenal sebagai dugaan tentang sifat fungsi yang dapat dihitung. Ini menyatakan bahwa untuk setiap fungsi yang dapat dihitung secara algoritmik pada bilangan asli, ada mesin Turing yang mampu menghitungnya. Atau, dengan kata lain, ada algoritma yang cocok untuk itu. Contoh keefektifan metode ini yang terkenal adalah uji tabel kebenaran untuk pengujian tautologi.
Cara untuk mencapai hasil yang diinginkan disebut "efektif", "sistematis" atau "mekanis" jika:
- Metode ditentukan dalam jumlah terbatas instruksi yang tepat, setiap instruksi diekspresikan menggunakan jumlah karakter yang terbatas.
- Ini akan berjalan tanpa kesalahan, akan menghasilkan hasil yang diinginkan dalam sejumlah langkah tertentu.
- Metode ini dapat dilakukan oleh manusia tanpa alat apapun selain kertas dan pensil
- Tidak memerlukan pemahaman, intuisi atau kecerdikan dari pihak yang melakukan tindakan
Sebelumnya dalam matematika, istilah informal "dapat dihitung secara efektif" digunakan untuk merujuk pada fungsi yang dapat dihitung dengan pensil dan kertas. Tetapi gagasan tentang komputabilitas algoritmik lebih intuitif daripada apa pun yang konkret. Sekarang ditandai dengan fungsi dengan argumen alami, yang memiliki algoritma perhitungan. Salah satu prestasi Alan Turing adalahrepresentasi dari predikat formal yang tepat, dengan bantuan yang dimungkinkan untuk menggantikan predikat informal, jika kondisi efisiensi metode digunakan. Gereja membuat penemuan yang sama.
Konsep dasar fungsi rekursif
Perubahan predikat Turing sepintas tampak berbeda dengan yang diajukan rekannya. Tetapi sebagai hasilnya, mereka ternyata setara, dalam arti bahwa masing-masing memilih himpunan fungsi matematika yang sama. Tesis Church-Turing adalah pernyataan bahwa himpunan ini berisi setiap fungsi yang nilainya dapat diperoleh dengan metode yang memenuhi kondisi efisiensi. Ada perbedaan lain antara kedua penemuan itu. Gereja hanya menganggap contoh bilangan bulat positif, sementara Turing menggambarkan karyanya mencakup fungsi yang dapat dihitung dengan variabel integral atau nyata.
Fungsi rekursif umum
Rumusan asli Church menyatakan bahwa perhitungan dapat dilakukan dengan menggunakan -kalkulus. Ini setara dengan menggunakan fungsi rekursif generik. Tesis Church-Turing mencakup lebih banyak jenis perhitungan daripada yang diperkirakan semula. Misalnya terkait cellular automata, kombinator, mesin registrasi dan sistem substitusi. Pada tahun 1933, matematikawan Kurt Gödel dan Jacques Herbrand menciptakan definisi formal kelas yang disebut fungsi rekursif umum. Ia menggunakan fungsi yang memungkinkan lebih dari satu argumen.
Membuat metode-kalkulus
Pada tahun 1936, Gereja Alonso menciptakan metode penentuan yang disebut -kalkulus. Dia dikaitkan dengan bilangan asli. Dalam -kalkulus, ilmuwan menentukan pengkodean mereka. Akibatnya, mereka disebut nomor Gereja. Sebuah fungsi yang didasarkan pada bilangan asli disebut -computable. Ada definisi lain. Fungsi dari tesis Church disebut -computable dalam dua kondisi. Yang pertama terdengar seperti ini: jika dihitung pada elemen Gereja, dan kondisi kedua adalah kemungkinan diwakili oleh anggota -kalkulus.
Juga pada tahun 1936, sebelum mempelajari karya rekannya, Turing menciptakan model teoretis untuk mesin abstrak yang sekarang dinamai menurut namanya. Mereka bisa melakukan perhitungan dengan memanipulasi karakter pada kaset. Ini juga berlaku untuk aktivitas matematika lain yang ditemukan dalam ilmu komputer teoretis, seperti komputasi probabilistik kuantum. Fungsi dari tesis Church baru kemudian dibuktikan menggunakan mesin Turing. Awalnya, mereka mengandalkan -kalkulus.
Komputabilitas fungsi
Ketika bilangan asli dikodekan dengan tepat sebagai urutan karakter, fungsi pada bilangan asli dikatakan Turing-computable jika mesin abstrak menemukan algoritme yang diperlukan dan mencetak fungsi ini pada pita. Perangkat seperti itu, yang tidak ada pada tahun 1930-an, di masa depan akan dianggap sebagai komputer. Mesin Turing abstrak dan tesis Gereja menandai era perkembanganperangkat komputasi. Terbukti bahwa kelas-kelas fungsi yang didefinisikan secara formal oleh kedua ilmuwan itu bertepatan. Oleh karena itu, sebagai hasilnya, kedua pernyataan digabungkan menjadi satu. Fungsi komputasi dan tesis Church juga memiliki pengaruh yang kuat terhadap konsep komputabilitas. Mereka juga menjadi alat penting untuk logika matematika dan teori pembuktian.
Pembenaran dan masalah metode
Ada pandangan yang bertentangan tentang tesis. Banyak bukti dikumpulkan untuk "hipotesis kerja" yang diajukan oleh Church dan Turing pada tahun 1936. Tetapi semua metode atau operasi yang diketahui untuk menemukan fungsi-fungsi baru yang dapat dihitung secara efektif dari fungsi-fungsi tertentu dihubungkan dengan metode-metode pembuatan mesin, yang saat itu belum ada. Untuk membuktikan tesis Church-Turing, dimulai dari fakta bahwa setiap model komputasi realistik adalah ekivalen.
Karena berbagai analisis yang berbeda, ini umumnya dianggap sebagai bukti yang sangat kuat. Semua upaya untuk secara lebih tepat mendefinisikan gagasan intuitif tentang fungsi yang dapat dihitung secara efektif ternyata setara. Setiap analisis yang telah diusulkan telah terbukti memilih kelas fungsi yang sama, yaitu fungsi yang dapat dihitung oleh mesin Turing. Tetapi beberapa model komputasi ternyata lebih efisien dalam hal waktu dan penggunaan memori untuk tugas yang berbeda. Belakangan diketahui bahwa konsep dasar fungsi rekursif dan tesis Church agak hipotetis.
Skripsi M
Penting untuk membedakan antara tesis Turing dan pernyataan bahwa apa pun yang dapat dihitung oleh perangkat komputasi dapat dihitung oleh mesinnya. Opsi kedua memiliki definisinya sendiri. Gandhi menyebut kalimat kedua "Thesis M". Bunyinya seperti ini: "Apa pun yang dapat dihitung oleh perangkat dapat dihitung oleh mesin Turing." Dalam arti sempit tesis adalah proposisi empiris yang nilai kebenarannya tidak diketahui. Tesis Turing dan "Tesis M" terkadang membingungkan. Versi kedua secara luas salah. Berbagai mesin kondisional telah dijelaskan yang dapat menghitung fungsi yang tidak dapat dihitung oleh Turing. Penting untuk dicatat bahwa tesis pertama tidak memerlukan yang kedua, tetapi konsisten dengan kepalsuannya.
Implikasi terbalik dari tesis
Dalam teori komputabilitas, tesis Church digunakan sebagai deskripsi pengertian komputabilitas oleh kelas fungsi rekursif umum. Stephen Kleene dari Amerika memberikan formulasi yang lebih umum. Dia menyebut sebagian rekursif semua fungsi parsial dapat dihitung oleh algoritma.
Implikasi terbalik biasanya disebut sebagai tesis terbalik Gereja. Itu terletak pada kenyataan bahwa setiap fungsi rekursif dari bilangan bulat positif dievaluasi secara efisien. Dalam arti sempit, tesis hanya menunjukkan kemungkinan seperti itu. Dan dalam arti yang lebih luas, ini abstrak dari pertanyaan apakah mesin kondisional ini dapat eksis di dalamnya.
Komputer kuantum
Konsep fungsi yang dapat dihitung dan tesis Church menjadi penemuan penting bagi matematika, teori mesin, dan banyak ilmu lainnya. Tetapi teknologi telah banyak berubah dan terus meningkat. Diasumsikan bahwa komputer kuantum dapat melakukan banyak tugas umum dengan waktu lebih sedikit daripada yang modern. Tapi pertanyaan tetap ada, seperti masalah berhenti. Komputer kuantum tidak dapat menjawabnya. Dan, menurut tesis Church-Turing, tidak ada perangkat komputasi lain juga.
