El sistema formal de Church se usa en computabilidad, lenguajes de programación y teoría de pruebas para representar funciones efectivas, programas y su computación y pruebas.
Solo estoy leyendo sobre el cálculo lambda para "conocerlo". Lo veo como una forma alternativa de cálculo en lugar de la máquina de Turing. Es una forma interesante de hacer cosas con funciones / reducciones (hablando en términos generales). Sin embargo, algunas preguntas me siguen...
¿Existe una relación entre la Máquina de Turing y el cálculo Lambda, o simplemente surgieron al mismo
Tengo tres preguntas secundarias relacionadas, que se destacan con viñetas a continuación (no, no se pueden dividir, si se lo pregunta). Andrej Bauer escribió, aquí , que algunas funciones son realizables a través de una máquina de Turing, pero no a través del cálculo lambda. Un paso clave de su...
¿Hay algún beneficio en el cálculo de la complejidad temporal de un algoritmo que utiliza cálculo lambda? ¿O hay otro sistema diseñado para este propósito? Cualquier referencia sería
En la introducción y explicación, las clases de complejidad P y NP a menudo se dan a través de la máquina Turing. Uno de los modelos de computación es el cálculo lambda. Entiendo que todos los modelos de computación son equivalentes (y si podemos introducir algo en términos de máquina de Turing,...
Actualmente estoy leyendo " Cálculo Lambda y Combinadores " de Hindley y Seldin. No soy un experto, pero siempre me ha interesado el cálculo lambda debido a su participación en la programación funcional (comenzando con Lisp y SICP, y ahora con R y Haskell). En " Cálculo binario lambda y lógica...
No puedo pensar en ningún modelo de este tipo, ¿tal vez alguna forma de cálculo lambda mecanografiado? algún autómata celular elemental? Esto casi refutaría el "Principio de equivalencia computacional" de Wolfram: Casi todos los procesos que obviamente no son simples pueden verse como cálculos...
He leído que inicialmente Church propuso el cálculo como parte de su artículo Postulados de lógica (que es una lectura densa). Pero Kleene demostró que su "sistema" era inconsistente, después de lo cual Church extrajo cosas relevantes para su trabajo sobre "computabilidad efectiva" y abandonó su...
En una categoría cartesiana cerrada ( CCC ), existen los llamados objetos exponenciales , escritas . Cuando un CCC es considerado como un modelo de la simplemente-mecanografiada λ -calculus , un objeto exponencial como B A caracteriza el espacio de la función de tipo A a tipo B . Un objeto...
Se dice que el CoC es la culminación de las tres dimensiones del Cubo Lambda. Esto no es aparente para mí en absoluto. Creo que entiendo las dimensiones individuales, y la combinación de cualquiera de los dos parece resultar en una unión relativamente sencilla (¿tal vez me falta algo?). Pero cuando...
Sé que la complejidad de la mayoría de las variedades de cálculos lambda mecanografiados sin la primitiva combinatoria Y está limitada, es decir, solo se pueden expresar funciones de complejidad limitada, con el límite cada vez mayor a medida que crece la expresividad del sistema de tipos. Recuerdo...
¿Existe un cálculo lambda tipificado donde la lógica correspondiente bajo la correspondencia de Curry-Howard es consistente y donde hay expresiones lambda tipificables para cada función computable? Esta es ciertamente una pregunta imprecisa, que carece de una definición precisa de "cálculo lambda...
Recientemente, Dana Scott propuso el cálculo lambda estocástico, un intento de introducir elementos probabilísticos en el cálculo lambda (sin tipo) basado en una semántica llamada modelo gráfico. Puede encontrar sus diapositivas en línea, por ejemplo, aquí y su artículo en Journal of Applied Logic...
Estoy interesado en el concepto de "integridad de r-Turing", según lo definido por Axelsen y Glück (2011) . Un sistema está completo en T-ruring si puede calcular el mismo conjunto de funciones que una máquina de Turing reversible, sin producir ningún dato "basura". Esto es lo mismo que poder...
¿Alguien puede explicar brevemente (si es posible!) O referirme a una referencia, resumiendo las diferencias entre el cálculo lambda sin tipo y los cálculos lambda con tipo más comunes? Estoy buscando particularmente declaraciones de su poder expresivo, equivalencias a sistemas lógicos /...
En un hilo reciente en la lista de correo de Agda, surgió la cuestión de las leyes , en la que Peter Hancock hizo un comentario estimulante .ηη\eta Tengo entendido que las leyes ηη\eta vienen con tipos negativos, es decir. conectivos cuyas reglas de introducción son invertibles. Para deshabilitar...
Sé que es imposible decidir la equivalencia para el cálculo lambda sin tipo. Citando a Barendregt, HP El cálculo Lambda: su sintaxis y semántica. Holanda Septentrional, Amsterdam (1984). :ββ\beta Si A y B son disjuntos, conjuntos no vacíos de términos lambda que están cerrados en igualdad,...
Creo que no lo entiendo, pero la conversión me parece una conversión que no hace nada, un caso especial de conversión donde el resultado es solo el término en la abstracción lambda porque no hay nada hacer, una especie de conversión sentido.β β βηη\etaββ\betaββ\betaββ\beta Entonces, tal vez...
Este artículo sugiere que hay combinadores (que representan cálculos simbólicos) que no pueden ser representados por el cálculo Lambda (si entiendo las cosas
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...