Quelles fonctions les expressions de calcul combinateur peuvent-elles calculer?

Une expression combinatoire (disons dans la base SK) peut être considérée comme une fonction qui mappe des expressions de calcul combinateur à des expressions de calcul combinateur. Autrement dit, on peut penser à une expression comme une fonction , où est l'ensemble de toutes les expressions de combinateur syntaxiquement valides dans la base SK. Ce mappage est effectué en appliquant l'entrée à l'expression, puis en la réduisant à la forme normale pour obtenir la sortie. $X$ $X:L \to L$ $L$

Étant donné que la base SK est complet Turing, on pourrait penser naïvement qu'il existe une expression SK qui implémente une fonction calculable de à . Cependant, ce n'est clairement pas le cas, car le résultat de la réduction sera toujours sous une forme normale. Cela signifie qu'il n'y a aucun moyen pour une expression d'avoir une sortie qui n'est pas sous une forme normale. $X$ $L$ $L$

Donc, à la place, je pourrais penser aux expressions de calcul SK comme mappant à , où est l'ensemble des expressions SK sous forme normale. Est-il vrai que, pour toute carte calculable , il existe une expression SK qui implémente cette carte? Ou existe-t-il d'autres restrictions sur l'ensemble des fonctions qui peuvent être calculées par les expressions de calcul combinateur de cette manière? $L'$ $L'$ $L'$ $f:L'\to L'$ $X$

lambda-calculus combinatory-logic Nathaniel
la source

Réponses:

Pour faire avancer les choses, et dans l'espoir que d'autres personnes donnent des réponses plus approfondies et plus détaillées sur la structure des fonctions -definable , permettez-moi de citer le corollaire 20.3.3 de The Lambda Calculus de Barendregts , Its Syntaxe et sémantique (alias "la Bible"). $\lambda$ $L'\to L'$

Corollaire 20.3.3: La fonction , définie par n'est pas définissable dans le -calculus non typé , c'est-à-dire qu'il n'y a pas de terme tel que pour tout . $\delta:L'^2\to L'$
$δ (M, N) = {\begin{cases} T r u e si M =_{β η} N \\ F une l s e autrement \end{cases}$ $\delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$ $\lambda$ $D$ $ré M N =_{β η} δ (M, N)$ $D\ M\ N =_{\beta\eta} \delta(M,N)$ $M,N\in L'$

La preuve implique des considérations sur les arbres de Böhm qui donnent une caractérisation assez forte des "actions" possibles de termes lambda arbitraires sur des formes normales. En particulier, pour tout terme fermé non constant , on peut trouver et tels que $F$ $n\in\mathbb{N}$ $P_1,\ldots,P_n$

F X P_{1} \dots P_{n} =_{β η} X Q_{1} \dots Q_{k}

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

Pour certains , . Cela contraint considérablement les formes possibles d'un hypothétique qui implémente , montrant avec un peu de travail qu'un tel ne peut pas exister. $k$ $Q_1,\ldots,Q_k$ $D$ $\delta$ $D$

cody
la source