He estado tratando de entender qué, por qué y cómo del cálculo pero no puedo entender "¿por qué funciona?"λλ\lambda "Intuitivamente" obtengo el modelo de computabilidad de Turing Machines (TM). Pero esta abstracción me deja confundido.λλ\lambda Supongamos que las TM no existen; entonces, ¿cómo...
Deje que los términos sizesizesize de λλ\lambda se definan de la siguiente manera: size(x)=1size(x)=1size(x) = 1 , size(λx.t)=size(t)+1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , size(ts)=size(t)+size(s)+1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Deje que la complejidad...
Estoy traduciendo un libro sobre LISP y, naturalmente, toca algunos elementos del cálculo . Entonces, una noción de extensionalidad se menciona allí junto con algunos modelos de cálculo λ , a saber: P ω y D ∞ (sí, con el infinito en la parte superior). Y se dice que P ω es extensional mientras que...
Es fácil ver en muchos libros de texto las pruebas de reducción de materia y fuerte normalización para el Sistema F, también, a veces hay definiciones de Sistema F con pares, donde (t, r) es un término, no solo una codificación. La pregunta es, ¿cuál sería la referencia para este...
La única definición de "cálculo" que conozco es el estudio de límites, derivados, integrales, etc. en el análisis. ¿En qué sentido es el cálculo lambda (o cosas como el cálculo mu) un "cálculo"? ¿Cómo se relaciona con el cálculo en el
Soy consciente de que el cálculo de construcciones se está normalizando fuertemente, lo que significa que cada expresión tiene una normalidad que no puede ser beta, eta-reducida aún más. De hecho, esta es la expresión más eficiente que calcula el mismo valor que la expresión original. Pero en...
¿Cuál es la diferencia de llamar a -calculus un álgebra en lugar de un cálculo? Planteo esta pregunta porque leí en alguna parte la línea " -calculus no es un cálculo sino un álgebra" (iirc, atribuido a Dana Scott). ¿Cual es el punto?
En la teoría de la complejidad, la definición de complejidad de tiempo y espacio hace referencia a una máquina universal de Turing: resp. la cantidad de pasos antes de detenerse y la cantidad de celdas en la cinta tocada. Dada la tesis de Church-Turing, también debería ser posible definir la...
El problema de representar las variables ligadas en la sintaxis, y en particular el de la sustitución para evitar la captura, es bien conocido y tiene una serie de soluciones: variables nombradas con equivalencia alfa, índices de Bruijn, anonimato local, conjuntos nominales, etc. Pero parece haber...
He leído sobre la sustitución hereditaria del cálculo simple de Lambda y del marco lógico con términos y tipos distintos. Me pregunto, ¿hay algún ejemplo de sustitución hereditaria en un sistema de tipo dependiente con una jerarquía universal? es decir, donde
¿Cuál es la relación entre el cálculo lambda simplemente escrito y la lógica de orden superior? Bajo Curry-Howard parece que el cálculo lambda simplemente escrito corresponde a la lógica proposicional. ¿Cómo se relaciona con la lógica de orden superior? Según este tutorial de Geuvers:...
Esto está inspirado en esta pregunta. Sea la colección de todos los combinadores que solo tienen dos variables ligadas. ¿ C es combinatoriamente completa?CC\mathcal{C}CC\mathcal{C} Creo que la respuesta es negativa, sin embargo, no pude encontrar una referencia para esto. También me interesarían...
He estado interesado en varios temas como Combinatory Logic, Lambda Calculus, Functional Programming por un tiempo y los he estado estudiando. Sin embargo, a diferencia de la "Teoría de la computación", que se esfuerza por responder a la pregunta de "computabilidad", es decir, cosas que pueden / no...
Estoy en una situación en la que necesito demostrar que la verificación de tipos es decidible para un cálculo de tipo dependiente en el que estoy trabajando. Hasta ahora, he podido demostrar que el sistema se está normalizando fuertemente y, por lo tanto, que la igualdad de definición es...
El siguiente término (usando índices bruijn): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Cuando se aplica a un número de iglesia se Nevalúa rápidamente a su forma normal en varios evaluadores existentes, incluidos los...
Del artículo de estrategia de evaluación en Wikipedia: La noción de estrategia de reducción en el cálculo lambda es similar pero distinta. Del artículo de estrategia de reducción en Wikipedia: Es similar pero sutilmente diferente de la noción de estrategia de evaluación en...
El siguiente término λ, aquí en forma normal: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implementa un algoritmo de clasificación para listas codificadas por la iglesia. Es decir, el...
Los combinadores de interacción se han propuesto antes como objetivo de compilación para el cálculo λ. Ese documento implementa el cálculo λ completo. También se sabe que es posible optimizar las codificaciones de la red de interacción del cálculo λ para el subconjunto de términos λ que es de tipo...
¿Alguien puede señalarme la referencia para la no definibilidad del módulo de continuidad funcional en PCF? \newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer ha escrito una muy buena publicación de blog explorando algunos de los problemas con más detalle, pero resumiré...
De manera equivalente, ¿existe una semántica denotacional conocida para los lenguajes de programación funcional probabilísticos de orden superior? Específicamente, ¿existe un modelo de dominio de cálculo puro sin tipo extendido por una operación de elección binaria aleatoria...