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

13

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 : L L LXX:LLL

É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.L LXLL

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 f : L L XLLLF:LLX

Nathaniel
la source

Réponses:

6

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").L L λLL

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 . δ ( M , N ) = { T r u e  si  M = β η N F a l s e  sinon λ D D M N = β η δ ( M , N ) M , N L δ:L2L

δ(M,N)={True si M=βηNFunelse autrement
λ
 M N=βηδ(M,N)
M,NL

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 FnNP1,,Pn

F X P1Pn=βηX Q1Qk

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.kQ1,,Qkδ

cody
la source