Fungsi Rekursif dan Mesin Register

Teori fungsi rekursif membangun fungsi-fungsi yang dapat dihitung dari beberapa operasi dasar, sementara mesin register menghitung dengan bilangan bulat yang disimpan dalam register, dua model yang mengapit mesin Turing dan menegaskan kekokohan komputabilitas.

Definition

Fungsi rekursif umum adalah fungsi yang dibangun dari konstanta, suksesor, dan proyeksi melalui komposisi, rekursi primitif, dan minimisasi tak terbatas; mesin register adalah perangkat abstrak yang menghitung dengan menaikkan, menurunkan, dan menguji isi dari sejumlah terbatas register yang menyimpan bilangan asli.

Scope

Topik ini mencakup fungsi rekursif primitif, penambahan minimisasi tak terbatas untuk memperoleh fungsi rekursif umum, fungsi Ackermann sebagai fungsi yang dapat dihitung yang bukan rekursif primitif, mesin register dan penghitung serta universalitasnya, dan kesetaraan semua model ini dengan komputabilitas Turing.

Core questions

• Bagaimana fungsi-fungsi yang dapat dihitung dapat didefinisikan secara aritmetika tanpa mesin apa pun?
• Mengapa minimisasi tak terbatas diperlukan di luar rekursi primitif?
• Bagaimana mesin register sederhana mencapai kekuatan komputasi penuh?
• Mengapa model aritmetika dan mesin ini bertepatan dengan mesin Turing?

Key theories

Kesetaraan dengan komputabilitas Turing

Fungsi rekursif umum dan fungsi yang dihitung oleh mesin register adalah persis fungsi yang dapat dihitung oleh Turing, memperkuat tesis Church–Turing melalui model yang didefinisikan dalam istilah aritmetika murni dan mesin elementer.

Melampaui rekursi primitif

Fungsi Ackermann bersifat total dan dapat dihitung namun tumbuh terlalu cepat untuk menjadi rekursif primitif, menunjukkan bahwa pencarian tak terbatas sangat penting dan bahwa fungsi rekursif primitif adalah subkelas yang tepat dari fungsi yang dapat dihitung.

Universalitas mesin register

Minsky menunjukkan bahwa mesin dengan hanya dua penghitung dan operasi penambahan, pengurangan, dan uji-nol sudah lengkap Turing (Turing-complete), sebuah demonstrasi ekstrem tentang seberapa sedikit struktur yang dibutuhkan komputasi penuh.

Clinical relevance

Mesin register memodelkan aritmetika bilangan bulat pada prosesor nyata secara lebih langsung dibandingkan pita, rekursi primitif sesuai dengan program yang selalu berakhir dan mendasari bahasa fungsional total serta analisis terminasi, dan pandangan fungsi rekursif menghubungkan komputasi dengan fondasi matematika.

History

Gödel dan Herbrand mendefinisikan fungsi rekursif umum pada awal tahun 1930-an, dan Kleene mengembangkan teorinya, termasuk peran minimisasi. Ackermann sebelumnya telah menunjukkan fungsi yang tumbuh cepat, dan Minsky memperkenalkan mesin register dan penghitung pada tahun 1960-an, membuktikan bahkan mesin dua-penghitung bersifat universal.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

Apa perbedaan antara fungsi rekursif primitif dan fungsi rekursif umum?

Fungsi rekursif primitif dibangun menggunakan perulangan terbatas dan selalu berakhir, tetapi tidak mencakup setiap fungsi yang dapat dihitung. Penambahan minimisasi tak terbatas, sebuah pencarian yang mungkin berjalan tanpa batas, menghasilkan fungsi rekursif umum, yang bertepatan persis dengan fungsi yang dapat dihitung oleh Turing.

Bagaimana mesin dengan hanya dua penghitung bisa sekuat komputer?

Minsky menunjukkan bahwa dua register yang menyimpan bilangan asli, dengan hanya operasi penambahan, pengurangan, dan uji-nol, dapat mensimulasikan mesin Turing dengan mengkodekan pitanya ke dalam register. Konstruksi ini sangat tidak efisien, tetapi membuktikan bahwa perangkat keras minimal sudah mencapai kekuatan komputasi penuh.