Le plus petit combinateur universel possible

17

Je recherche le plus petit combinateur universel possible , mesuré par le nombre d'abstractions et d'applications nécessaires pour spécifier un tel combinateur dans le calcul lambda . Exemples de combinateurs universels:

  • taille 23: λf.f (fS (KKKI)) K
  • taille 18: λf.f (fS (KK)) K
  • taille 14: λf.fKSK
  • taille 12: λf.fS (λxyz.x)
  • taille 11: λf.fSK

où S = λxyz.xz (yz) de taille 6 et K = λxy.x de taille 2 sont les combinateurs du calcul du combinateur SK . Les 4 premiers exemples sont décrits dans cet article .

Mes questions sont:

  • Existe-t-il des combinateurs universels de plus petite taille?
  • Quel est le plus petit combinateur universel possible?

EDIT: Voir également /math//a/180263/76284 , qui a λazbc.bc(a(λy.c))(qui serait de taille 8 , correspondant à la somme des tailles de la base SK). Quelqu'un sait-il comment exprimer S et K à partir de ce combinateur?

lo.logic computability lambda-calculus universal-computation combinatory-logic user76284
la source
Peut-être que cela vous intéresse: wolframscience.com/nksonline/page-1123a-text?firstview=1
Andrej Bauer
Quelle est votre définition de la taille? Pouvez-vous l'écrire en tant que fonction?
Joshua Herman
Puisque 6 + 2 = 8 <11, cela me fait me demander si {S, K} est la plus petite base de combinateurs mesurée par la taille totale?
Noam Zeilberger
Votre modification récente ressemble plutôt à une réponse (partielle).
Emil Jeřábek soutient Monica
Dans quelle mesure définissez-vous strictement " combinateur "? Doivent-ils être de la forme λx*.Eoù Eest sans abstraction?
Peter Taylor

Réponses:

9

Il convient de noter qu'il est toujours difficile de trouver des combinateurs avec certaines propriétés de réduction , et trouver le plus petit tel combinateur peut facilement être indécidable (pour des raisons triviales, car il peut être indécidable de prouver qu'une certaine application du combinateur s'arrête même).

Il existe plusieurs questions ouvertes simples de même saveur, par exemple les problèmes # 4, # 6 et # 10 de la liste des problèmes ouverts de TLCA .

Une chose à noter est que votre combinateur doit certainement avoir au moins 2 variables liées, dont l'une est dupliquée (comme tout ensemble complet de combinateurs) et une doit être effacée. Cela met une borne inférieure de 4, je pense (2 abstractions et 2 apparitions d'une variable), qui n'est pas si loin de la borne supérieure de 11.

Edit: les commentaires et la référence de Noam poussent la borne inférieure à 5! Je ne serais pas surpris si la preuve nécessite également que la variable supplémentaire apparaisse également, ce qui nous pousserait à 6.

cody
la source
3
En fait, deux variables ne suffisent pas ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), donc cela donne une limite inférieure légèrement supérieure (taille 5 = 3 abstractions et 2 applications).
Noam Zeilberger
@NoamZeilberger bien, c'est un résultat fantastique dont je n'étais pas au courant!
cody
7

Pour votre première question, je crois que ce document peut aider un tas. Il a un calcul combinateur 6 bits qui est également un UTM. De plus, il a un combinateur universel qui semble avoir une taille 7 avec un élément étant donné ce que vous voulez. Ils l'appellent Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Je ne sais pas si vous pouvez dire ou prouver qu'il existe un combinateur minimal. Le document suggère qu'il devrait être au moins inférieur à 6 bits.

Joshua Herman
la source
2
Le combinateur de Zot est en fait le dernier répertorié dans l'OP: λx.xSK (partagé avec ses langues parentes, Iota et Jot), qui a une longueur 11. Dans le "calcul combinateur 6 bits" (Keraia), le "6 bits" est la taille de l'UTM; et il semble que ce soit juste un encodage du calcul lambda, pas un calcul combinateur (et donc n'a pas de combinateur universel intégré).
2012rcampion