Tesis Church–Turing

Tesis Church–Turing menyatakan bahwa setiap fungsi yang dapat dihitung oleh prosedur efektif apa pun dapat dihitung oleh mesin Turing, menyamakan gagasan informal tentang algoritma dengan model matematika yang tepat.

Definition

Tesis Church–Turing adalah klaim bahwa fungsi-fungsi yang secara intuitif dapat dihitung adalah persis fungsi-fungsi yang dapat dihitung oleh mesin Turing, atau secara ekuivalen oleh kalkulus lambda atau fungsi rekursif umum; ini adalah tesis daripada teorema karena gagasan intuitif tidak didefinisikan secara formal.

Scope

Topik ini mencakup pernyataan tesis, bukti konvergen dari model-model yang diajukan secara independen, perbedaan antara tesis asli tentang komputabilitas efektif dan varian fisik atau teoretis kompleksitas yang lebih kuat, serta peran tesis sebagai jembatan antara intuisi dan bukti formal dalam teori komputabilitas.

Core questions

• Apa artinya mengidentifikasi gagasan informal tentang algoritma dengan model formal?
• Mengapa konvergensi model independen dianggap sebagai bukti kuat untuk tesis ini?
• Apakah tesis ini merupakan teorema matematika, definisi, atau klaim empiris?
• Bagaimana versi fisik dan teoretis kompleksitas melampaui pernyataan aslinya?

Key theories

Konvergensi model komputasi

Mesin Turing, kalkulus lambda Church, dan fungsi rekursif Gödel dan Herbrand terbukti mendefinisikan kelas fungsi yang persis sama, dan kesepakatan independen ini adalah bukti utama yang diajukan untuk tesis tersebut.

Status sebagai tesis, bukan teorema

Karena gagasan intuitif tentang prosedur efektif tidak diformalkan, klaim tersebut tidak dapat dibuktikan; ini diterima sebagai identifikasi fundamental yang memungkinkan argumen algoritmik informal menggantikan konstruksi mesin Turing formal.

Clinical relevance

Tesis ini mengizinkan praktik sehari-hari dalam mendeskripsikan algoritma dalam pseudokode tingkat tinggi daripada sebagai mesin Turing, karena setiap gagasan yang masuk akal tentang prosedur efektif diasumsikan setara dengan Turing; tesis ini juga membingkai perdebatan tentang apakah perangkat fisik atau kuantum dapat menghitung di luar komputasi Turing.

History

Pada tahun 1936, Church mengusulkan untuk mengidentifikasi kalkulabilitas efektif dengan lambda-definability, dan Turing secara independen mengemukakan model mesinnya, setelah itu Turing, Kleene, dan lainnya membuktikan bahwa ini dan fungsi rekursif adalah ekuivalen. Gödel, yang awalnya skeptis, kemudian menganggap analisis Turing sebagai konklusif, dan klaim gabungan tersebut dikenal sebagai tesis Church–Turing.

Debates

Dapatkah komputasi fisik melampaui batas Turing?

Tesis asli berkaitan dengan prosedur efektif, tetapi versi fisik yang lebih kuat mengklaim bahwa tidak ada perangkat yang dapat direalisasikan secara fisik yang dapat menghitung fungsi yang tidak dapat dihitung oleh Turing. Proposal untuk hiperkomputasi dan implikasi mekanika kuantum membuat klaim yang diperluas ini tetap diperdebatkan, meskipun tesis klasik pada dasarnya tetap tidak tertandingi.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

Mengapa disebut tesis daripada teorema?

Ini menghubungkan model formal dengan gagasan informal tentang prosedur efektif, dan gagasan informal itu tidak memiliki definisi matematika untuk membuktikan sesuatu. Bukti kuatnya adalah bahwa setiap upaya independen untuk memformalkan komputasi telah menghasilkan kelas fungsi yang sama, tetapi dukungan ini bersifat konseptual daripada bukti.

Apakah komputer kuantum menyangkal tesis Church–Turing?

Tidak. Komputer kuantum mungkin memecahkan beberapa masalah lebih cepat, tetapi mereka menghitung kelas fungsi yang persis sama dengan mesin Turing, sehingga tesis asli tentang apa yang dapat dihitung tetap berlaku. Sebaliknya, mereka berkaitan dengan versi teoretis kompleksitas yang lebih kuat yang berfokus pada efisiensi daripada komputabilitas.