Base incomplète de combinateurs

Ceci est inspiré par cette question. Soit la collection de tous les combinateurs qui n'ont que deux variables liées. La combinaison est-elle complète? $\mathcal{C}$ $\mathcal{C}$

Je pense que la réponse est négative, mais je n'ai pas pu trouver de référence pour cela. Je serais également intéressé par des références pour des preuves d'incomplétude combinatoire d'ensembles de combinateurs (je peux voir pourquoi l'ensemble composé de combinateurs avec une seule variable liée est incomplet, donc ces ensembles devraient contenir plus que de simples éléments de ). $\mathcal{D}$ $\mathcal{D}$

lo.logic lambda-calculus combinatory-logic tci
la source

Pourriez-vous clarifier ce que vous entendez par le nombre de variables liées d'un combinateur (= terme lambda fermé)? Nombre total d'abstractions lambda?

Noam Zeilberger

Oui, c'est ce que je voulais dire.

tci

En fait, peut-être que ce n'est pas exactement ce que vous vouliez dire ... peut-être plutôt que vous voulez dire le nombre total de variables distinctes utilisées dans les abstractions lambda, de sorte que par exemple

a deux variables liées distinctes, malgré quatre abstractions lambda? Dans ce cas, il apparaît que Rick Statman a répondu exactement à cette question (négativement), dans " Deux variables ne suffisent pas ".

(λ x . x (λ y . y)) (λ x . λ y . x y)

$(\lambda x.x(\lambda y.y))(\lambda x.\lambda y.x y)$

Noam Zeilberger

Droite. Je pense que c'est la réponse que je cherchais, et je m'attendais vraiment à ce que ce soit le résultat de Statman. Je n'ai pas encore vérifié, mais je pense que cela donnerait également une réponse négative à la question que j'ai mentionnée. Si vous le postez comme réponse, je l'accepterais avec plaisir.

tci

Réponses:

[Élargir le commentaire en réponse.]

Tout d'abord, juste une clarification sur le comptage des variables liées dans un combinateur (= terme fermé) . J'interprète la question comme demandant sorte que par exemple le terme compte comme ayant deux variables liées, malgré quatre liants (c.-à-d. abstractions lambda). Cette façon de compter était initialement un peu étrange pour moi car elle n'est pas invariante sous $t$

the total number of distinct bound variable names in t

$\text{the total number of distinct bound variable names in }t$

t = (λ x . x (λ y . y)) (λ x . λ y . y x)

$t = (\lambda x.x(\lambda y.y))(\lambda x.\lambda y.yx)$

Conversion

: par exemple,

est

équivalent à

, mais

a quatre noms de variables liés distincts. Cependant, ce n'est pas vraiment un problème, car lenombreminimumde noms de variables liées distinctes nécessaires pour écrire un terme fermé

est égal au

α

$\alpha$

t

$t$

α

$\alpha$

t^{'} = (λ x . x (λ y . y)) (λ a . λ b . b a)

$t' = (\lambda x.x(\lambda y.y))(\lambda a.\lambda b.ba)$

t^{'}

$t'$

t

$t$

le nombre maximum de variables libres dans un sous-terme de t

$\text{the maximum number of free variables in a subterm of }t$ et cette dernière notion est invariante sous

conversion.

α

$\alpha$

Donc, soit la collection de tous les combinateurs qui peuvent être écrits en utilisant au plus deux variables liées distinctes, ou de manière équivalente la collection de tous les combinateurs dont les sous-termes ont au plus deux variables libres. $\mathcal{C}$

Théorème (Statman) : n'est pas combinatoire complet. $\mathcal{C}$

Il semble que la preuve originale de cela soit contenue dans un rapport technique de Rick Statman:

Combinateurs héréditairement de l'ordre deux. Rapport technique 88-33 de Carnegie Mellon Math Department, août 1988. ( pdf )

Statman définit une collection essentiellement isomorphe de combinateurs qu'il appelle "HOT", pour "héréditaire d'ordre deux". Le rapport technique montre en fait que le problème de mot (c'est-à-dire, égalité) pour HOT est encore indécidable, malgré le fait qu'il n'est pas combinatoire complet. Statman a ensuite écrit un court article autonome avec la preuve que HOT n'est pas complet en combinatoire dans: $\beta$

Deux variables ne suffisent pas. Actes de la 9e conférence italienne sur l'informatique théorique, pp. 406-409, 2005. ( acm )

$Hn$ $Hn$ $n+1$ $\beta$ $n$ $S = \lambda x.\lambda y.\lambda z.(xz)(yz)$ $n$ $n$ $Hn$ $n+1$

Noam Zeilberger
la source