Para preguntas sobre sistemas lógicos definidos mediante la aplicación y reescritura de términos de combinadores. Estos sistemas suelen tener una estrecha conexión con el cálculo lambda.
En la página de Wikipedia para Fixed Point Combinators está escrito el texto bastante misterioso. El combinador Y es un ejemplo de lo que hace que el cálculo Lambda sea inconsistente. Por lo tanto, debe considerarse con sospecha. Sin embargo, es seguro considerar el combinador Y cuando se define...
El combinador de punto fijo FIX (también conocido como el combinador Y) en el cálculo lambda ( tipo) ( ) se define como:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y....
La mayoría de nosotros conocemos la correspondencia entre la lógica combinatoria y el cálculo lambda . Pero nunca he visto (tal vez no he mirado lo suficientemente profundo) el equivalente de "combinadores mecanografiados", correspondiente al cálculo lambda simplemente mecanografiado. ¿Existe tal...
Es bien sabido que los combinadores S y K forman una base para el cálculo del combinador, en el sentido de que todos los demás combinadores pueden expresarse en términos de ellos. También está la base B, C, K, W de Curry, que tiene la misma propiedad. Debe haber un número infinito de tales bases,...
El combinador Y tiene el tipo . Según la correspondencia de Curry-Howard, debido a que el tipo ( a → a ) → a está habitado, debe corresponder a un verdadero teorema. Sin embargo, a → a siempre es cierto, por lo que parece que el tipo del combinador Y corresponde al teorema a , que no siempre es...
Una expresión combinatoria (digamos en la base SK) puede considerarse como una función que asigna expresiones de cálculo combinador a expresiones de cálculo combinador. Es decir, se puede pensar en una expresión como una función X : L → L , donde L es el conjunto de todas las expresiones de...
Según Peter Selinger , The Lambda Calculus is Algebraic (PDF). Al principio de este artículo dice: Se sabe que la interpretación combinatoria del cálculo lambda es imperfecta porque no satisface la regla : según la interpretación, M = N no implica \ lambda xM = \ lambda xN (Barendregt,...
Específicamente, si un nuevo como lugar de sería el cálculo de {{S, K_2, I \} una base competitiva?K2K2K_2K2=λx.(λy.y)K2=λX.(λy.y)K_2 = \lambda x. (\lambda y. y)K=λx.(λy.x)K=λX.(λy.X)K = \lambda x. (\lambda y. x){S,K2,I}{S,K2,I}\{S, K_2,I\} Mi suposición es "no", solo porque parece que no...
Por lo tanto, existe un algoritmo para convertir los términos de cálculo lambda en lógica combinatoria utilizando los combinadores SK. Produce cosas que explotan en tamaño. Me gustaría saber más sobre esta explosión de tamaño. Sin embargo, no puedo pensar en un algoritmo mejor. He oído hablar de...
En el artículo de Chris Okasaki " Combinadores de aplanamiento: sobrevivir sin paréntesis ", muestra que dos combinadores son suficientes y necesarios como base para codificar expresiones completas de Turing sin la necesidad de un operador de aplicación o paréntesis. En comparación con las...
Como hay un cálculo lambda sin tipo y un cálculo lambda de tipo simple (como se describe, por ejemplo, en el libro Tipos y lenguajes de programación de Benjamin Pierce), ¿existe una lógica combinatoria de tipo simple? Por ejemplo, parecería que los tipos naturales para los combinadores S, K y yo...
Entiendo lo que es, pero no veo cómo sirve para algoritmos ni nada. Tal vez me estoy perdiendo algo. Necesito que alguien me dé un ejemplo de cómo se puede usar para poder entenderlo