Apakah teorema smn konsep yang sama dengan kari?

Saya mempelajari teorema smn dan konsepnya mengingatkan saya pada kari.

Dari artikel wikipedia tentang teorema smn :

teorema mengatakan bahwa untuk bahasa pemrograman yang diberikan dan bilangan bulat positif m dan n, ada algoritma tertentu yang menerima sebagai input kode sumber program dengan variabel bebas m + n, bersama dengan nilai m. Algoritma ini menghasilkan kode sumber yang secara efektif menggantikan nilai-nilai untuk variabel bebas m pertama, meninggalkan sisa variabel bebas.

Dari sebuah artikel tentang kari :

Secara intuitif, currying mengatakan "jika Anda memperbaiki beberapa argumen, Anda mendapatkan fungsi dari argumen yang tersisa"

Sepertinya ide yang sama bagi saya. Satu-satunya alasan mengapa saya tidak yakin adalah bahwa materi yang saya temui di smn tidak menyebutkan kari (dan sebaliknya), jadi saya ingin berkonsultasi untuk memastikan saya benar-benar mendapatkannya.

computability emanek
sumber

Memang. Beberapa bukti komputabilitas memiliki rasa seperti daging domba. Teorema smn, sangat kasar, memungkinkan untuk berpura-pura bahwa indeks fungsi rekursif adalah istilah lambda, sehingga dengan diberikan kita dapat membuat informal dan klaim bahwa adalah primitif rekursif. Bahkan bukti teorema rekursi kedua (yang mengeksploitasi smn) adalah combinator titik tetap Gereja yang menyamar, tersembunyi di balik penggunaan . Poin kunci di sini adalah bahwa meskipun enumerasi didefinisikan enumerasi, katakanlah, TM (atau Java, atau ...) kita masih bisa berpura-pura memiliki lambda!

ϕ_{i} (-, -)

$\phi_i(-,-)$

g (x) = # λ y . ϕ_{i} (x, y)

$g(x) = \#\lambda y. \phi_i(x,y)$

g

$g$

s ()

$s()$

ϕ_{i}

$\phi_i$

chi

Nah, smn membuat pernyataan eksistensial sementara keberadaan fungsi kari menyediakan "kompiler". Tapi idenya sama.

Raphael

Jawaban:

Ya, itu adalah hal yang sama.

Currying adalah konsep dari -calculus. Ini adalah transformasi antara dan . Anggap ini sebagai "jika kita memiliki fungsi dua argumen tipe dan , maka kita dapat memperbaiki argumen pertama (tipe ), dan kita akan mendapatkan fungsi argumen yang tersisa (tipe )". Sebenarnya, transformasi ini adalah isomorfisme. Ini dibuat secara matematis tepat dengan model matematika dari (diketik) -calculus, yang merupakan kategori tertutup kartesian . $\lambda$ $A \times B \to C$ $A \to (B \to C)$ $A$ $B$ $A$ $B$ $\lambda$

Ada kategori set bernomor. Himpunan bernomor adalah pasangan mana adalah himpunan dan adalah surjection parsial , yaitu peta dari angka ke , yang mungkin juga tidak terdefinisi. Jika maka kita mengatakan bahwa adalah kode dari . Dalam teori komputabilitas ada banyak contoh. Setiap kali kami menyandikan beberapa informasi dengan angka, kami mendapatkan set bernomor. Sebagai contoh, ada penomoran standar dari fungsi yang dapat dihitung sebagian, sehingga adalah angka yang dihitung oleh fungsi sebagian yang dapat dihitung yang dikodekan oleh $(A, \nu_A)$ $A$ $\nu_A : \mathbb{N} \to A$ $A$ $\nu_A(n) = x$ $n$ $x$ $\varphi$ $\varphi_n(k)$ $n$ ketika diterapkan pada . (Hasilnya mungkin tidak terdefinisi.) $k$

Morfisme himpunan bernomor adalah peta terealisasi , yang berarti ada sedemikian rupa sehingga untuk semua dalam domain . Ini terlihat rumit, tetapi yang dikatakannya adalah melakukan kode apa yang dilakukan terhadap elemen. Ini adalah cara matematika untuk mengatakan bahwa "program mengimplementasikan fungsi ". $f : (A, \nu_A) \to (B, \nu_B)$ $n \in \mathbb{N}$ $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ $k$ $\nu_A$ $\varphi_n$ $f$ $\phi_n$ $f$

Inilah lucunya: kategori set bernomor ditutup kartesian. Karena itu, kita dapat menginterpretasikan -calulus yang diketik di dalamnya, dan menanyakan program apa yang mengimplementasikan operasi kari. Jawabannya adalah: program yang diberikan oleh teorema smn. $\lambda$

Andrej Bauer
sumber

Menarik. Apakah kategori itu terkait erat dengan ? tampaknya menginduksi PER.

P E R (A)

$PER(A)$

ν_{A}

$\nu_A$

chi

Ya, kedua kategori itu setara, dan versi yang setara ketiga adalah set sederhana (lihat "set sederhana dan rakitan").

Andrej Bauer