El combinador universal más pequeño posible

17

Estoy buscando el combinador universal más pequeño posible , medido por el número de abstracciones y aplicaciones requeridas para especificar dicho combinador en el cálculo lambda . Los ejemplos de combinadores universales incluyen:

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

donde S = λxyz.xz (yz) de tamaño 6 y K = λxy.x de tamaño 2 son los combinadores del cálculo del combinador SK . Los primeros 4 ejemplos se describen en este documento .

Mis preguntas son:

  • ¿Hay algún combinador universal que sea más pequeño?
  • ¿Cuál es el combinador universal más pequeño posible?

EDITAR: Consulte también /math//a/180263/76284 , que tiene λazbc.bc(a(λy.c))(que sería de tamaño 8 , que coincide con la suma de tamaños de la base SK). ¿Alguien sabe cómo expresar S y K de este combinador?

lo.logic computability lambda-calculus universal-computation combinatory-logic usuario76284
fuente
Tal vez esto sea de interés: wolframscience.com/nksonline/page-1123a-text?firstview=1
Andrej Bauer
¿Cuál es tu definición de talla? ¿Puedes escribirlo como una función?
Joshua Herman el
Como 6 + 2 = 8 <11, esto me hace preguntarme si {S, K} es la base más pequeña de combinadores medidos por el tamaño total.
Noam Zeilberger
Su edición reciente suena más bien como una respuesta (parcial).
Emil Jeřábek apoya a Monica el
¿Cuán estrictamente estás definiendo " combinador "? ¿Tiene que ser de la forma λx*.Edonde Eestá libre de abstracción?
Peter Taylor

Respuestas:

9

Cabe señalar que encontrar combinadores con ciertas propiedades de reducción siempre es difícil, y encontrar el combinador más pequeño puede ser fácilmente indecidible (por razones triviales, ya que puede ser indecidible probar que cierta aplicación del combinador incluso se detiene).

Hay varias preguntas abiertas simples de un sabor similar, por ejemplo, problemas # 4, # 6 y # 10 de la lista TLCA de problemas abiertos .

Una cosa a tener en cuenta es que su combinador ciertamente necesita tener al menos 2 variables ligadas, una de las cuales está duplicada (como cualquier conjunto completo de combinadores) y una necesita ser borrada. Creo que esto pone un límite inferior de 4 (2 abstracciones y 2 apariencias de una variable), que no está muy lejos del límite superior de 11.

Editar: ¡los comentarios y la referencia de Noam llevan el límite inferior a 5! No me sorprendería si la prueba también requiere que aparezca la variable adicional, lo que nos llevaría a 6.

cody
fuente
3
En realidad, dos variables no son suficientes ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), por lo que esto proporciona un límite inferior ligeramente mayor (tamaño 5 = 3 abstracciones y 2 aplicaciones).
Noam Zeilberger
@NoamZeilberger bien, ¡ese es un resultado fantástico del que no estaba al tanto!
cody
7

Para su primera pregunta, creo que este documento puede ayudar mucho. Tiene un cálculo combinador de 6 bits que también es un UTM. También tiene un combinador universal que parece tener un tamaño 7 con un elemento dado lo que quieres. Lo llaman Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

No estoy seguro de si puedes decir o probar que hay un combinador mínimo. El documento sugeriría que tendría que tener al menos menos de 6 bits.

Joshua Herman
fuente
2
El combinador de Zot es en realidad el último listado en el OP: λx.xSK (compartido con sus idiomas principales, Iota y Jot), que tiene una longitud 11. En el "cálculo del combinador de 6 bits" (Keraia), el "6 bits" es el tamaño de la UTM; y parece que es solo una codificación del cálculo lambda, no un cálculo combinador (y, por lo tanto, no tiene un combinador universal incorporado).
2012 Arcampion