Clasificación de los cálculos lambda tipificados / sin tipo

18

¿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 / aritméticos o métodos de cálculo, y analogías con lenguajes de programación, si corresponde.

Si bien tengo la intención de leer, algo así como una tabla de referencia que describe los cálculos y sus equivalencias / diferencias / lugar en la jerarquía sería una ENORME referencia para ayudarme a resolverlos.

No digo que lo siguiente sea correcto, solo trato de esbozar algunas de las impresiones que tengo que ver si al menos sirven como punto de partida (¡o algo para corregir!)

Cálculo lambda sin tipo - ec. a la lógica de primer orden: no se puede hacer X

Simplemente tecleó cálculo lambda - eq a ... lógica, relacionada con Lisp?

Calc lambda 'polimórfica', etc.

Cálculo de construcciones: ¿lógica intuicionista?

Lógica combinatoria - comparable a ??? cálculo lambda mecanografiado, relacionado con el tipo de lenguajes APL / J

Si esto se vincula con el cubo lambda y sus tres ejes, mejor.

Si bien estoy familiarizado con los conceptos básicos del cálculo lambda y la programación con lenguajes funcionales, nunca he entendido ni hecho conexiones significativas con los sistemas de tipos involucrados y los diferentes sabores de los cálculos lambda (¿y quizás pi?).

Cuando intento investigar esto, no puedo evitar encontrarme desviado, abriendo muchas pestañas del navegador y bifurcando en tantas direcciones que nunca entro en ninguna de ellas con tanta profundidad.

No estoy seguro de si lo que estoy pidiendo es razonable, pero espero que al menos haya pintado lo suficiente como para sugerir alguna lectura que pueda explicar lo que estoy buscando.

jon_darkstar
fuente
1
una visualización del cubo lambda, si tal vez se refiera a él puede ayudar con la explicación rbjones.com/rbjpub/logic/cl/tlc001.htm
jon_darkstar
3
Una historia personal: cuando estaba aprendiendo por primera vez el cálculo lambda con y sin tipo, siempre me confundía el por qué debería preocuparme por los cálculos completos sin Turing escritos. Esto a menudo me hizo perder el interés. Por otro lado, nunca me molestó esto al pensar en la complejidad y la computación eficiente. Finalmente, alguien conectó los dos hilos por mí en esta respuesta y ahora puedo entender mejor por qué pasó tanto tiempo enseñándome cálculo lambda mecanografiado.
Artem Kaznatcheev
Veo que lo.logicse ha agregado una etiqueta. probablemente una pregunta tonta, pero ¿qué significa eso exactamente?
jon_darkstar 05 de
"Cuando intento investigar esto, no puedo evitar encontrarme desviado, abriendo muchas pestañas del navegador y bifurcándome en tantas direcciones que nunca entro en ninguna de ellas con tanta profundidad". <- Este soy yo, todo el tiempo! Gracias por preguntar lo que he estado pensando ...
agam

Respuestas:

26

Tu mesa está un poco confundida; Aquí hay uno mejor.

  • Cálculo lambda sin tipo: no hay interpretación lógica, como señala Andrej
  • Cálculo lambda simplemente tipado - lógica proposicional intuicionista
  • Cálculo lambda polimórfico: lógica pura de segundo orden (es decir, sin cuantificadores de primer orden)
  • Tipos dependientes: generalización de la lógica de primer orden
  • Cálculo de construcciones: generalización de la lógica de orden superior

La dependencia de tipo es más general que la cuantificación de primer orden, ya que convierte las pruebas en objetos que puede cuantificar. Existen cálculos Lambda que corresponden al FOL intuicionista ordinario, pero no se usan lo suficiente como para tener un nombre especial: las personas tienden a ir directamente a los tipos dependientes.

También puede relacionar la forma sintáctica de un cálculo con los sistemas lógicos.

  • Cálculos combinados (p. Ej., Combinadores de SKI): sistemas de estilo Hilbert
  • A-forma normal - cálculo consecuente
  • Cálculo lambda tipificado ordinario - deducción natural
Neel Krishnaswami
fuente
¡fantástico! Gracias. me ayuda a cuenta de la motivación / distinción de estos diferentes cálculos, y sin duda ayudará a mantener un conocimiento de base cuando leí más sobre él
jon_darkstar
También incluiría cálculos lambda mecanografiados sin interpretación lógica, como PCF. Además, hay muchos cálculos lambda geniales que corresponden a otra lógica, como el cálculo lambda lineal.
Sam Tobin-Hochstadt
@ Sam: Buen punto. "Ninguna interpretación lógica" es realmente demasiado fuerte, ya que realmente significa "autorreferencia ilimitada permitida", lo que combinado con la reutilización variable conduce a una inconsistencia. Pero algunas teorías basadas en lógica lineal apoyan esquemas de comprensión ingenuos sin ninguna inconsistencia.
Neel Krishnaswami
sin duda, algunas formas en que puede agregar algunas cosas al cálculo lambda sin ser inconsistente. Pero hay muchos cálculos lambda interesantes, mecanografiados, sin interpretación lógica, exactamente en el sentido del cálculo lambda no tipificado.
Sam Tobin-Hochstadt
20

λλλnatλ0T

λλ

λλ

λλλUlambda : U -> (U -> U)gamma : (U -> U) -> UλUλCUU[Cop,Set]UUU

Referencias

Andrej Bauer
fuente