Pentingnya rekursi dalam teori komputabilitas

Dikatakan bahwa teori komputasi juga disebut teori rekursi. Kenapa disebut seperti itu? Mengapa rekursi memiliki kepentingan sebesar ini?

Pada 1920-an dan 1930-an orang berusaha mencari tahu apa artinya "secara efektif menghitung fungsi" (ingat, tidak ada mesin komputasi tujuan umum di sekitarnya, dan komputasi adalah sesuatu yang dilakukan oleh orang-orang).

Beberapa definisi "computable" diusulkan, di antaranya tiga paling dikenal:

1. The -calculus$\lambda$
2. Fungsi rekursif
3. Mesin turing

Ini ternyata mendefinisikan kelas yang sama fungsi angka-teori. Karena fungsi rekursif lebih tua dari mesin Turing, dan bahkan lebih lama -calculus tidak langsung diterima sebagai gagasan yang memadai tentang komputabilitas, kata sifat "rekursif" digunakan secara luas (fungsi rekursif, set rekursif, set rekursif rekursif, dll.)$\lambda$

Belakangan, ada upaya, yang dipopulerkan oleh Robert Soare , untuk mengubah "rekursif" menjadi "dapat dihitung". Jadi kita saat ini berbicara tentang fungsi yang dapat dihitung dan set yang dapat dihitung. Tetapi banyak buku teks lama, dan banyak orang, masih lebih suka terminologi "rekursif".

Begitu banyak untuk sejarah. Kita juga dapat bertanya apakah rekursi penting untuk perhitungan dari sudut pandang matematika murni. Jawabannya sangat pasti "ya!". Rekursi terletak pada dasar bahasa pemrograman tujuan umum (bahkan whileloop hanyalah bentuk rekursi karena while p do csama dengan if p then (c; while p do c)), dan banyak struktur data fundamental, seperti daftar dan pohon, bersifat rekursif. Rekursi tidak bisa dihindari dalam ilmu komputer, dan dalam teori komputabilitas secara khusus.

Teori komputabilitas adalah studi tentang fungsi yang dapat dihitung :-).

Fungsi seperti itu biasanya (dalam komunitas ini) didefinisikan sebagai fungsi yang dapat diekspresikan dengan mesin Turing.

Secara lebih formal fungsi dapat dihitung jika ada Turing sehingga jika input ke adalah output dari adalah T T x = 1 n T 1 f ( x )$f: \mathbb{N} \mapsto \mathbb{N}$$T$$T$$x = 1^n$$T$$1^{f(x)}.$

Ternyata jika Anda mendefinisikan fungsi yang dapat dihitung dengan cara ini (program) mereka setara dengan serangkaian fungsi yang dapat diperoleh dengan menggunakan aturan yang dijelaskan di sini . Mereka disebut fungsi rekursif karena salah satu aturan untuk mendapatkan fungsi tersebut adalah definisi rekursif (Lihat aturan 5 di wikipedia).

Jadi alasan mengapa teori rekursi memiliki banyak kepentingan adalah setara dengan pertanyaan mengapa fungsi komputasi penting. Dan jawaban untuk yang terakhir harus cukup jelas :)