Fungsi Komputabel dan Tesis Church-Turing

Fungsi komputabel adalah fungsi yang dapat dievaluasi oleh prosedur mekanis, dan tesis Church-Turing mengidentifikasi gagasan informal ini dengan beberapa model matematis presisi yang semuanya mendefinisikan kelas yang sama.

Definition

Suatu fungsi dikatakan komputabel jika beberapa mesin Turing, atau secara ekuivalen beberapa definisi rekursif parsial, menghasilkan keluarannya pada setiap masukan di mana fungsi tersebut didefinisikan; tesis Church-Turing menegaskan bahwa kelas matematis yang presisi ini bertepatan dengan kelas intuitif fungsi yang dapat dihitung secara efektif.

Scope

Topik ini mencakup mesin Turing, fungsi rekursif parsial yang dibangun dari fungsi dasar melalui komposisi, rekursi primitif, dan minimisasi, kalkulus lambda dan mesin register, bukti bahwa model-model ini ekuivalen, mesin universal, dan tesis Church-Turing yang menyatakan bahwa model-model ini mencakup semua komputasi efektif.

Core questions

• Apa itu mesin Turing dan bagaimana mesin ini mendefinisikan komputasi?
• Bagaimana fungsi rekursif parsial dihasilkan dari operasi dasar?
• Mengapa semua model komputasi yang masuk akal mendefinisikan fungsi yang sama?
• Apa status dan signifikansi tesis Church-Turing?

Key theories

Model mesin Turing

Mesin Turing adalah perangkat berstatus terbatas yang beroperasi pada pita tak terbatas, dan fungsi-fungsi yang dihitungnya memformalkan gagasan algoritma dalam hal manipulasi simbol elementer.

Ekuivalensi model

Mesin Turing, fungsi rekursif parsial, kalkulus lambda, dan mesin register semuanya menghitung kelas fungsi yang sama persis, menunjukkan kekokohan gagasan komputabilitas.

Mesin universal dan enumerasi

Ada mesin Turing universal yang mensimulasikan mesin apa pun yang diberikan kodenya, sehingga fungsi komputabel dapat dihitung secara efektif dan diperlakukan sebagai data, dasar dari hasil referensi diri.

Clinical relevance

Gagasan tentang fungsi komputabel adalah fondasi ilmu komputer teoretis: mesin universal mendahului komputer program tersimpan, ekuivalensi model membenarkan definisi algoritma tunggal yang kuat, dan kerangka kerja ini menyediakan pengaturan yang presisi di mana ketidakterpecahan (undecidability) dan kompleksitas dipelajari.

History

Pada tahun 1936, Church mendefinisikan keterhitungan efektif melalui kalkulus lambda dan Turing melalui mesinnya, dan kedua gagasan tersebut segera terbukti ekuivalen dengan fungsi rekursif Kleene. Tesis Church-Turing yang dihasilkan menjadi definisi algoritma yang diterima, dan mesin universal Turing menjadi nenek moyang konseptual komputer serbaguna.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Apakah ada fungsi yang tidak komputabel?

Ya. Karena program dapat dihitung tetapi fungsi tidak, argumen penghitungan menunjukkan sebagian besar fungsi tidak komputabel, dan contoh spesifik seperti fungsi penghentian terbukti tidak dapat dihitung. Komputabilitas adalah batasan nyata pada fungsi mana yang dapat dievaluasi oleh algoritma.

Apakah tesis Church-Turing membatasi apa yang dapat dilakukan komputer?

Tesis ini menyatakan bahwa tidak ada model komputasi efektif yang memperluas kelas fungsi komputabel di luar mesin Turing. Perangkat keras yang lebih cepat atau arsitektur yang berbeda mengubah efisiensi, bukan batas dari apa yang secara prinsip dapat dihitung, sehingga tesis ini menetapkan batas absolut pada keterpecahan algoritmik.