Le calcul SK2 est-il une base complète, où K2 est le combinateur K inversé?

10

Plus précisément, si j'ai défini un nouveau comme au lieu de le -calcul serait-il une base concurrentielle?K2

K2=λx.(λy.y)
K=λx.(λy.x)
{S,K2,I}

Ma supposition est "non", simplement parce que je ne peux pas sembler être capable de construire le combinateur K régulier à partir des combinateurs , et , mais je n'ai pas d'algorithme à suivre, ni une bonne intuition à faire des choses avec ces combinateurs.SIK2

Il semble que vous puissiez définir avec le calcul régulier , mais je ne pouvais pas vraiment travailler en arrière à partir de cela pour obtenir une dérivation de en termes de et le reste.

K2=KI
{S,K,(I)}KK2

Ma tentative de prouver qu'elle n'était pas fonctionnellement complète a essentiellement tenté de construire de manière exhaustive toutes les fonctions réalisables à partir de ces combinateurs afin de montrer que vous atteignez une impasse (une fonction que vous avez déjà vue), quels que soient les combinateurs que vous utilisez. Je me rends compte que cela ne va pas nécessairement être vrai pour les ensembles de combinateurs fonctionnellement incomplets (par exemple, le combinateur K seul ne sera jamais sans issue lorsqu'il est appliqué à lui-même), mais c'était ma meilleure pensée. J'ai toujours pu utiliser le combinateur S pour me faufiler hors de ce que je pensais être finalement une impasse, donc je ne suis plus aussi sûr de la faisabilité de cette approche.

J'ai posé cette question sur StackOverflow mais j'ai été encouragé à la poster ici. J'ai reçu quelques commentaires sur ce post, mais je ne suis pas sûr de les avoir bien compris.

Bonus: si ce n'est pas une base complète, la langue résultante est-elle néanmoins Turing-complete?

cole
la source
c'est un joli puzzle. Il semble que S et K 'ne vous permettent de générer que des termes dont les formes normales de tête ont jusqu'à trois λs en tête (c'est-à-dire des termes qui se normalisent à la forme λx₁.λx₂.λx₃. Xᵢ t₁ ... tₙ), de sorte que cela pourrait être une autre voie pour prouver l'inachèvement, même si cela semble un peu difficile à formaliser. Mais vous n'atteignez certainement jamais une "impasse": commencez par définir I = λx.x = K2 K2, puis en répétant la transformation t ↦ S t K2, vous pouvez exprimer λx.x I ... I pour n'importe quelle chaîne de Is .
Noam Zeilberger
... Et désolé, par "incomplétude", j'entends l'inachèvement de SK 'comme base combinatoire pour le calcul lambda non typé. Je n'ai pas non plus une bonne intuition pour savoir s'il s'agit de Turing-complete (ce qui serait impliqué par l'exhaustivité combinatoire, mais pas l'inverse).
Noam Zeilberger
Post -cross: stackoverflow.com/q/55148283/781723 , cs.stackexchange.com/q/108741/755 . Veuillez ne pas poster la même question sur plusieurs sites . Chaque communauté devrait avoir une chance honnête de répondre sans perdre de temps.
DW
Mon erreur @DW, puis-je faire quelque chose pour y remédier?
cole

Réponses:

14

Considérez les termes du calcul comme des arbres (avec des nœuds binaires représentant des applications et des feuilles représentant les combinateurs.S,K2,IS,K2

Par exemple, le terme serait représenté par l'arbreS(SS)K2

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

A chaque arbre associez sa feuille la plus à droite, celle que vous obtenez en prenant la branche droite à chacune . Par exemple, la feuille la plus à droite de l'arbre ci-dessus est .TK 2@K2

Comme on peut le voir dans l'art ASCII ci-dessous, toutes les règles de réduction dans le calcul conservent la feuille la plus à droite.S,K2,I

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f                 
  / \
 /   \
S     e
      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

À partir de là, il est facile de voir que si un terme réduit à , alors et ont la même feuille la plus à droite. Par conséquent, il n'y a pas de terme dans le calcul tel que réduit à . Cependant, réduit à , donc ne peut pas être exprimé dans le calculTTTTTS,K2,ITK2SK2KK2SK2KS,K2,I

ZAK
la source
Très bel argument!
Noam Zeilberger
Argument très lisse et clair. Je vous remercie. Je vais peut-être ouvrir une question distincte à poser sur l'intégralité de Turing.
cole
5

EDIT: Comme le soulignent les commentaires, ce n'est qu'une réponse partielle, car elle ne s'applique qu'au calcul simplement tapé (ou plutôt, cela montre qu'il n'y a pas de définition possible de K qui ne contient pas de mauvais sous-terme typé). S'il n'y a pas d'objection, je ne le supprimerai pas, car il présente une technique de preuve très productive pour le paramètre tapé.S,K2,I


Rappelons que nos combinateurs ont les types suivants (style Curry, donc sont variables):A,B,C

  • K:ABA
  • K2:ABB
  • S:(ABC)(AB)(AC)
  • I:AA

Par la correspondance de Curry-Howard, si nous pouvons exprimer en termes de alors le calcul de preuve de style Hilbert avec trois axiomes logiques et une règle d'inférence (de et inférer ) montre la formule .KI,S,K2ABB,(ABC)(AB)(AC),AAAABBABA

Mais nous pouvons donner une t,f,usémantique à trois valeurs (valeurs ) à la connective telle que les formules , et obtiennent la valeur de toute interprétation.ABB(ABC)(AB)(AC)AAt

A B | A -> B
t t | t
t f | f
f t | t
f f | t
t u | f
f u | t
u t | t
u f | f
u u | t

Cette sémantique est clairement saine dans le sens où chaque conséquence des axiomes obtient la valeur sous chaque interprétation (elle n'est pas complète, il y a des choses qui obtiennent toujours la valeur mais que nous ne pouvons pas réellement prouver). Cependant, obtient la valeur selon l'interprétation qui attribue à et à , et est donc pas prouvable des axiomes correspondant à .K2,S,IA B A A B S , K 2 , IttABAfuAtBS,K2,I

ZAK
la source
1
J'aime l'approche, mais pourriez-vous préciser quelles règles vous prenez comme calcul séquentiel?
Noam Zeilberger
Pouvez-vous esquisser comment prouver S dans ce calcul séquentiel restreint? Cela ne semble pas possible avec les règles que je suppose que vous pourriez vouloir dire.
Robin Houston
1
@ robin-houston: veuillez voir ma modification (j'ai également ajouté un argument sémantique différent avec la même conclusion).
ZAK
2
Je suis d'accord avec Charles Stewart (ici: twitter.com/txtpf/status/1123962607306706944 ) qu'il n'est pas clair comment passer de l'inhabitation dans le calcul lambda simplement tapé à l'inexpressibilité à l'aide de combinateurs. Il pourrait y avoir un argument spécifique pour K, mais l'étape initiale "... alors on pourrait aussi faire la même chose dans le λ-calcul simplement tapé" ne tient pas en général (Charles a mentionné le contre-exemple du combinateur Y) . Pensez-vous rendre cet argument rigoureux?
Noam Zeilberger
1
@NoamZeilberger Je suis également d'accord. Cet argument semble malheureusement insuffisant: dans le calcul non typé, vous pourriez être en mesure d'obtenir utilisant une construction qui implique des (sous) termes qui n'ont pas de type. Il faut prouver que si vous pouvez y parvenir, vous pouvez également faire de même en utilisant uniquement des termes dactylographiés, mais cela me semble difficile à prouver. K
chi