Menulis fungsi rekursif universal [tertutup]

9

Apakah ada konstruksi eksplisit singkat dari fungsi rekursif universal ? Semua definisi yang saya lihat melibatkan penomoran mesin Turing dalam beberapa cara, yang mungkin namun tampaknya sulit dan tidak dapat dikelola untuk menulis dalam bahasa pemrograman tingkat tinggi (seperti Python, Haskell dll.)

lo.logic computability pl.programming-languages sdcvvc
sumber
Pertanyaan awalnya ditanyakan di SO , sepertinya lebih tepat di sini.
sdcvvc
1
Pemahaman saya adalah bahwa apa yang dilakukan fungsi rekursif universal adalah tepatnya untuk memberikan penomoran fungsi rekursif (atau mesin Turing yang setara) sehingga hasilnya dapat dihitung dari indeks fungsi rekursif dan input. Oleh karena itu "fungsi rekursif universal tanpa penomoran mesin Turing" tidak terdengar masuk akal bagi saya.
Tsuyoshi Ito
3
Bukan tingkat penelitian. Setiap juru bahasa untuk bahasa Turing-complete adalah fungsi rekursif universal.
Warren Schudy

Jawaban:

1

Bagaimana dengan penerjemah Lisp asli McCarthy (asal di sini )? Ini universal, bekerja pada pengodean alami (a Lisp AST), tidak bergantung pada penerjemah eksternal, dan sekitar 20 baris.

pron
sumber
13

Tentu. Tulis rutin yang menghitung masing-masing fungsi rekursif primitif Godel , dan tulis rutin untuk operator pencarian yang tidak terikat. Himpunan fungsi yang dapat Anda hitung dengan cara ini setara dengan himpunan fungsi yang dapat dihitung oleh mesin Turing. Informasi lebih lanjut di sini .

Kelemahannya adalah setiap input untuk program universal Anda perlu dibingkai dalam hal operasi sederhana tersebut. Tentu saja, itu untuk apa kompiler.

Aaron Sterling
sumber
10

Penerjemah apa pun untuk bahasa apa pun yang lengkap Turing adalah fungsi rekursif universal. Ada penerjemah untuk bahasa tingkat tinggi seperti C ++ atau Python.

Penomoran godel ada, tetapi secara implisit. Misalnya, kode C ++ menghitung fungsi rekursif adalah indeks untuk .ggg

Kaveh
sumber
Penerjemah untuk Mesin Turing (atau Mesin Register, atau fungsi rekursif) juga merupakan fungsi rekursif universal, dan tidak sulit untuk mengimplementasikannya. Saya telah mengimplementasikannya di C ++ beberapa tahun yang lalu, dan saya cukup yakin bahwa itu akan lebih sederhana dengan Python. Gunakan Google, ada banyak simulator gratis di Internet, dan beberapa di antaranya bahkan open-source.
Kaveh
8

Fungsi universal udapat ditulis dengan mudah dalam bahasa mirip Haskell (tanpa efek samping, fungsi tingkat tinggi), yaitu:

u f x = f x

Fungsi ubersifat universal karena menerima (deskripsi) program fdan rekaman masukan x, dan memberitahu Anda hasil yang berjalan fdi x.

Walaupun jawaban ini tidak sepenuhnya serius, ia menunjukkan bahwa kompiler atau juru bahasa Haskell seperti sudah berisi semua bagian bangunan yang diperlukan untuk fungsi universal. Moral dari cerita ini adalah bahwa waktu lebih baik dihabiskan untuk mempelajari bagaimana kompiler dan penerjemah bekerja daripada khawatir tentang menerapkan fungsi universal dalam hal mesin Turing.

Andrej Bauer
sumber
Namun, umengambil fungsi - Saya akan menyebutnya fungsi tingkat tinggi. Saya ingin umengambil integer, atau tipe data aljabar biasa. Saya tidak memaksakan model komputasi spesifik apa pun, asalkan argumennya uberwujud - misalnya, ia dapat diserialisasi dari / ke string.
sdcvvc
Pada mesin yang sebenarnya (setelah kode dikompilasi) umengambil penutup, yang merupakan urutan byte yang terbatas. Bahkan dalam teorema utm biasa integer yang umengambil mewakili suatu fungsi.
Andrej Bauer
5

Periksa juga makalah ini oleh John Tromp, menggunakan logika kombinasi. Tulisan sebelumnya, tampaknya tidak lagi tersedia, bahkan lebih rapi.

Yuval Filmus
sumber