Específicamente, si un nuevo como
lugar de
sería el cálculo de {{S, K_2, I \} una base competitiva?
Mi suposición es "no", solo porque parece que no puedo construir el combinador K normal a partir de los combinadores , y , pero no tengo un algoritmo que seguir, ni tengo una buena intuición. sobre hacer cosas de estos combinadores.
Parece que puedes definir
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 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 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?
Respuestas:
Considere los términos del cálculoS, K2, I como árboles (con nodos binarios que representan aplicaciones, y las hojas S, K2 representan los combinadores.
Por ejemplo, el términoS( SS) K2 estaría representado por el árbol
A cada árbolT asocia su hoja más a la derecha, la que obtienes al tomar la rama derecha en cada una K2 .
@
. Por ejemplo, la hoja más a la derecha del árbol de arriba esComo se puede ver en el arte ASCII a continuación, todas las reglas de reducción en el cálculoS, K2, I preservan la hoja más a la derecha.
A partir de ahí, es fácil ver que si algún términoT 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
fuente
EDITAR: Como señalan los comentarios, esta es solo una respuesta parcial, ya que se aplica solo al cálculo simple deS,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 queA,B,C son variables):
t,f,u
t
t
t
f
u
t
fuente