Fungsi apa yang dapat dihitung oleh kalkulus kalkulus?

Ekspresi kombinator (misalkan dalam basis SK) dapat dianggap sebagai fungsi yang memetakan ekspresi kalkulus kombinator ke ekspresi kalkulus kombinator. Artinya, seseorang dapat menganggap ekspresi $X$ sebagai fungsi , di mana adalah himpunan semua ekspresi kombinator yang valid secara sintaksis dalam basis SK. Pemetaan ini dilakukan dengan menerapkan input ke ekspresi, dan kemudian mengurangi ke bentuk normal untuk mendapatkan output. $X:L \to L$ $L$

Karena dasar SK tersebut Turing lengkap, satu mungkin naif berpikir bahwa ada sebuah SK ekspresi yang mengimplementasikan fungsi dihitung dari ke . Namun, ini jelas bukan masalahnya, karena hasil reduksi akan selalu dalam bentuk normal. Ini berarti tidak ada cara bagi ekspresi untuk memiliki output yang tidak dalam bentuk normal. $X$ $L$ $L$

Jadi sebagai gantinya, saya bisa menganggap ekspresi kalkulus SK sebagai pemetaan ke , di mana adalah himpunan ekspresi SK dalam bentuk normal. Apakah itu kasus bahwa, untuk peta yang dapat dihitung , ada ekspresi SK yang mengimplementasikan peta ini? Atau adakah batasan lebih lanjut pada himpunan fungsi yang dapat dihitung dengan ekspresi kalkulus kombinator dengan cara ini? $L'$ $L'$ $L'$ $f:L'\to L'$ $X$

lambda-calculus combinatory-logic Nathaniel
sumber

Jawaban:

Untuk membuat bola bergulir, dan dengan harapan orang lain memberikan jawaban yang lebih dalam dan lebih rinci pada struktur fungsi -definisi , izinkan saya mengutip Corollary 20.3.3 dari Barendregts ' The Lambda Calculus, Syntax dan Semantik (alias "Alkitab"). $\lambda$ $L'\to L'$

Akibat wajar 20.3.3: Fungsi , yang didefinisikan oleh tidak didefinisikan dalam untyped - kalkulus, yaitu tidak ada istilah sehingga $\delta:L'^2\to L'$
$δ (M., N) = {\begin{cases} T r kamu e jika M. =_{β η} N \\ F Sebuah l s e jika tidak \end{cases}$ $\delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$ $\lambda$ $D$ $D M. N =_{β η} δ (M., N)$ $D\ M\ N =_{\beta\eta} \delta(M,N)$ untuk semua . $M,N\in L'$

Buktinya melibatkan pertimbangan pada pohon Böhm yang memberikan karakterisasi yang agak kuat tentang "tindakan" yang mungkin dari istilah lambda sewenang-wenang pada bentuk normal. Secara khusus, untuk setiap non-konstan jangka tertutup , di dapat menemukan dan sehingga $F$ $n\in\mathbb{N}$ $P_1,\ldots,P_n$

F x P_{1} ... P_{n} =_{β η} x Q_{1} ... Q_{k}

$F\ x\ P_1\ldots P_n =_{\beta\eta} x\ Q_1\ldots Q_k$

$k$ $Q_1,\ldots,Q_k$ $D$ $\delta$ $D$

cody
sumber