¿Es el cálculo SK2 una base completa, donde K2 es el combinador de K invertido?

10

Específicamente, si un nuevo como lugar de sería el cálculo de {{S, K_2, I \} una base competitiva?K2

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

Mi suposición es "no", solo porque parece que no puedo construir el combinador K normal a partir de los combinadores S , I y K2 , pero no tengo un algoritmo que seguir, ni tengo una buena intuición. sobre hacer cosas de estos combinadores.

Parece que puedes definir

K2=KI
con el cálculo regular {S,K,(I)} , pero realmente no pude trabajar hacia atrás para obtener una derivación de K en términos de K2 y el resto.

Mi intento de demostrar que no estaba funcionalmente completo esencialmente intentó construir exhaustivamente todas las funciones que se pueden obtener de estos combinadores para mostrar que alcanzas un callejón sin salida (una función que has visto antes) sin importar qué combinadores uses. Me doy cuenta de que esto no necesariamente será cierto para conjuntos de combinadores funcionalmente incompletos (por ejemplo, el combinador K por sí solo nunca tendrá un punto muerto cuando se aplica a sí mismo), pero este fue mi mejor pensamiento. Siempre pude usar el combinador S para escabullirme de lo que pensé que finalmente era un callejón sin salida, por lo que ya no estoy tan seguro de la viabilidad de este enfoque.

Hice esta pregunta en StackOverflow pero me animaron a publicarla aquí. Recibí algunos comentarios sobre esa publicación, pero no estoy seguro de haberlos entendido bien.

Bonificación: si no es una base completa, ¿el lenguaje resultante es Turing completo?

col
fuente
Este es un buen rompecabezas. Parece que S y K 'solo le permiten generar términos cuyas formas normales de cabeza tienen hasta tres λs principales (es decir, términos que se normalizan a la forma λx₁.λx₂.λx₃. Xᵢ t₁ ... tₙ), por lo que podría ser Otra ruta para probar la incompletitud, aunque parece un poco complicado formalizar. Sin embargo, definitivamente nunca llega a un "callejón sin salida": comience definiendo I = λx.x = K2 K2, luego repitiendo la transformación t ↦ S t K2 puede expresar λx.x I ... I para cualquier cadena de Is .
Noam Zeilberger
... Y lo siento, por "incompletitud", me refiero a la incompletitud de SK 'como una base combinatoria para el cálculo lambda sin tipo. Tampoco tengo una buena intuición sobre si es o no Turing completo (lo que estaría implícito en la integridad combinatoria, pero no al revés).
Noam Zeilberger
Publicación cruzada: stackoverflow.com/q/55148283/781723 , cs.stackexchange.com/q/108741/755 . Por favor, no publicar la misma pregunta en varios sitios . Cada comunidad debe tener una oportunidad honesta de responder sin perder el tiempo de nadie.
DW
Mi error @DW, ¿hay algo que pueda hacer para remediar esto?
cole

Respuestas:

14

Considere los términos del cálculo S,K2,yo como árboles (con nodos binarios que representan aplicaciones, y las hojas S,K2 representan los combinadores.

Por ejemplo, el término S(SS)K2 estaría representado por el árbol

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

A cada árbol T asocia su hoja más a la derecha, la que obtienes al tomar la rama derecha en cada una @. Por ejemplo, la hoja más a la derecha del árbol de arriba es K2 .

Como se puede ver en el arte ASCII a continuación, todas las reglas de reducción en el cálculo S,K2,yo preservan la hoja más a la derecha.

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

A partir de ahí, es fácil ver que si algún término T reduce a T , entonces T y T tienen la misma hoja más a la derecha. Por lo tanto, no hay término T en el cálculo , deS,K2,I modo que TK2S reduzca a K2 . Sin embargo, KK2S reduce a K2 , por lo tanto, K no puede expresarse en el cálculo S,K2,I

ZAK
fuente
Muy buen argumento!
Noam Zeilberger
Muy hábil y claro argumento. Gracias. Quizás abriré una pregunta por separado para preguntar sobre la integridad de Turing.
cole
5

EDITAR: Como señalan los comentarios, esta es solo una respuesta parcial, ya que se aplica solo al cálculo simple de S,K2,I (o más bien, muestra que no hay una definición posible de K que no contenga un subterm mal escrito). Si no hay objeción, no la eliminaré, ya que presenta una técnica de prueba muy productiva para la configuración escrita.


Recuerde que nuestros combinadores tienen los siguientes tipos (estilo Curry, por lo que A,B,C son variables):

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

KI,S,K2ABB,(ABC)(AB)(AC),AAAABBABA

t,f,uABB(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

K2,S,IttABAfuAtBS,K2,I

ZAK
fuente
1
Me gusta el enfoque, pero ¿podría aclarar qué reglas está tomando como cálculo posterior?
Noam Zeilberger
¿Puedes esbozar cómo probar S en este cálculo secuencial restringido? No parece posible con las reglas que supuse que querías decir.
Robin Houston,
1
@ robin-houston: vea mi edición (también he agregado un argumento semántico diferente con la misma conclusión).
ZAK
2
Estoy de acuerdo con Charles Stewart (aquí: twitter.com/txtpf/status/1123962607306706944 ) en que no está claro cómo pasar de la deshabitación en el cálculo lambda de tipo simple a la inexpresabilidad usando combinadores. Puede haber un argumento específico para K, pero el paso inicial "... entonces uno también podría hacer lo mismo en el cálculo λ simplemente tipado" no es válido en general (Charles mencionó el contraejemplo del combinador Y) . ¿Ves de hacer este argumento riguroso?
Noam Zeilberger
1
K