Primitive Recursive Functions untuk Programmer Praktis

Fungsi rekursif primitif: panduan untuk programmer praktis

Programmer sering menggunakan istilah "Turing-complete". Di domain tertentu, ketidak-Turing-complete kadang dianggap sebagai keutamaan atau persyaratan. Namun, sebagian besar diskusi didasarkan pada informasi yang keliru. Arti sebenarnya dari tidak Turing-complete berbeda. Turing-completeness adalah istilah matematis dengan makna yang sangat spesifik. Istilah ini tidak boleh ditafsirkan ulang untuk kegunaan lain.

Part I: Ringkasan

• Jika sebuah program yang ditulis dalam bahasa Turing-complete berjalan lebih cepat daripada O(22N), maka program itu juga dapat diimplementasikan dalam bahasa yang tidak Turing-complete.
• Sebagian besar masalah praktis lebih cepat daripada "dua dari dua dari dua".
• Bahasa yang tidak Turing-complete tidak memberikan batasan praktis.
• Program yang tidak berhenti, atau membutuhkan waktu sangat lama untuk berhenti, diperlakukan sama.

Part II: Cara kerja mesin

Mesin keadaan hingga (Finite State Machines)

• Mesin keadaan hingga menerima string sebagai masukan dan mengembalikan "ya" atau "tidak".
• Memiliki jumlah state yang terbatas.
• Fungsi transisi state menerima state saat ini dan simbol masukan berikutnya, lalu mengembalikan state baru.
• Mesin keadaan hingga tidak dapat masuk ke loop tak hingga.
• Mesin keadaan hingga memiliki daya ekspresi yang sama dengan regular expression.

Mesin Turing (Turing Machines)

• Mesin Turing sedikit lebih kompleks daripada mesin keadaan hingga.
• Mesin Turing bekerja dengan menggunakan tape yang dapat berubah-ubah.
• Fungsi transisi state menerima state saat ini dan simbol saat ini pada tape, lalu mengembalikan state baru, simbol baru, dan arah gerak.
• Mesin Turing bekerja sebagai fungsi dan dapat masuk ke loop tak hingga.
• Mesin Turing dapat mensimulasikan mesin keadaan hingga.

Pemrograman mesin Turing

• Mesin Turing memiliki tape tak hingga.
• Mesin Turing tidak menjalankan program yang diberikan pengguna. Program di-hardcode ke dalam mesin.
• Universal Turing Machine dapat mensimulasikan mesin Turing lain.
• Mesin Turing memiliki kemampuan komputasi yang sama dengan bahasa seperti Python.

Batasan mesin Turing

• Ada fungsi yang tidak dapat diimplementasikan dengan mesin Turing.
• Kita dapat membuat daftar semua mesin Turing, tetapi tidak semua fungsi dapat didaftarkan.
• Masalah tertentu (misalnya, halting problem) tidak dapat diselesaikan dengan mesin Turing.
• Kekuatan mesin Turing membuat kita tidak bisa menentukan apakah sebuah program akan berhenti.

Part III: Kembali ke masalah praktis

Fungsi rekursif primitif (Primitive Recursive Functions)

• Fungsi rekursif primitif adalah fungsi yang menerima tuple bilangan natural sebagai masukan dan mengembalikan bilangan natural.
• Fungsi-fungsi lain disusun mulai dari fungsi zero dan succ.
• Rekursi umum tidak diizinkan, tetapi bentuk loop yang terbatas diizinkan.
• Operasi seperti penjumlahan, perkalian, dan perpangkatan dapat didefinisikan.
• Operator logika dan pernyataan kondisional dapat didefinisikan.
• Angka digunakan untuk merepresentasikan struktur data.

Ringkasan GN⁺

• Artikel ini ditulis untuk membantu memahami Turing-completeness dan fungsi rekursif primitif.
• Menjelaskan apa arti praktis dari tidak Turing-complete.
• Menjelaskan perbedaan antara mesin keadaan hingga dan mesin Turing, serta membahas batasan mesin Turing.
• Menjelaskan definisi dan cara penggunaan fungsi rekursif primitif.
• Artikel ini akan membantu programmer meningkatkan pemahaman mereka tentang Turing-completeness dan fungsi rekursif primitif.
• Proyek dengan fungsi serupa antara lain "regular expression" dan "mesin keadaan hingga".