¿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 mecanografiado". Básicamente me pregunto si hay (a) ejemplos conocidos de esto, o (b) pruebas de imposibilidad conocidas para algo en esta área.
Editar: @cody da una versión precisa de esta pregunta en su respuesta a continuación: ¿existe un sistema de tipo puro lógico (LPTS) que sea consistente y Turing completo (en el sentido que se define a continuación)?
type-theory
lambda-calculus
typed-lambda-calculus
curry-howard
Morgan Thomas
fuente
fuente
Respuestas:
Muy bien, le diré algo: en general, para un sistema de tipo dado , lo siguiente es cierto:T
La prueba generalmente procede asumiendo que tiene un término de tipo F a l s e , utilizando la reducción de sujeto para obtener una forma normal, y luego procediendo por inducción en la estructura de dicho término para obtener una contradicción.a b s u r d F a l s e
Es natural preguntarse si lo contrario es válido, es decir
El problema con esto es que no existe una noción real más general de "sistema de tipos", y aún menos acuerdo sobre el significado de consistencia lógica para tales sistemas. Sin embargo, podemos verificar empíricamente que
¿Cómo se relaciona esto con la integridad de Turing? Bueno, por un lado, si la verificación de tipo es decidible , entonces el argumento de Andrej muestra que uno de los siguientes debe ser válido:
Esto tiende a sugerir que:
Dar un teorema real en lugar de una sugerencia requiere hacer que la noción de sistemas de tipos e interpretaciones lógicas sea matemáticamente precisa.
Ahora me vienen a la mente dos comentarios:
Hay un sistema de tipos indecidible , el sistema de tipos de intersección que tiene una interpretación lógica y puede representar cada término normalizador . Como observa, esto no es lo mismo que ser Turing completo, ya que el tipo de una función total puede necesitar actualizarse (refinarse, de hecho) antes de aplicarlo al argumento deseado. El cálculo es un cálculo de "estilo curry" y es igual a STLC + Γ ⊢ M : τλ
y
Γ⊢M:τ∩σ
Hay una clase de sistemas de tipos, los Sistemas de Tipos Puros , en los que tal pregunta podría hacerse precisa. En este marco, sin embargo, la interpretación lógica es menos clara. Uno podría estar tentado a decir: "un PTS es consistente si tiene un tipo deshabitado". Pero esto no funciona, ya que los tipos pueden vivir en diferentes "universos", donde algunos pueden ser consistentes y otros no. Coquand y Herbelin definen una noción de sistemas lógicos de tipo puro , en la que la pregunta tiene sentido y muestran
Lo que responde a la pregunta en una dirección (inconsistente TC) en este caso. Hasta donde sé, la pregunta para LPTS general todavía está abierta y es bastante difícil.⇒
Editar: ¡ Lo contrario del resultado Coquand-Herbelin no es tan fácil como pensaba! Esto es lo que se me ocurrió hasta ahora.
Un sistema lógico de tipo puro es un PTS con (al menos) los tipos y T y p e , (al menos) el axioma P r o p : T y p e y (al menos) la regla ( P r o p , P r o p , P r o p ) , con el requisito adicional de que no hay ningún tipo de tipo P r o p .P r o p T y p e P r o p : T y p e ( P r o p , P r o p , P r o p ) P r o p
Ahora voy a asumir una declaración particular de integridad de Turing: arreglar un LPTS y dejar que Γ sea el contextoL Γ
esTuring Completoiff para cada función computable total f : N → N hay un término t f tal que Γ ⊢ t f : n a t → n a t y para cada n ∈ N t f ( S n 0 ) → ∗ β S f ( n ) 0L F: N → N tF
Ahora, el argumento de diagonalización de Andrej muestra que hay no terminantes de tipo n a t .t n a t
¡Ahora parece que estamos a medio camino! Dado un término que no termina , queremos reemplazar las ocurrencias de n a t por algún tipo genérico A y deshacernos de 0 y S en Γ , y tendremos nuestra inconsistencia ( A está habitada en el contexto A : P r o p )!Γ ⊢ l o o p : n a t n a t UN 0 0 S Γ UN A : P r o p
Desafortunadamente, aquí es donde me quedo atascado, ya que es fácil reemplazar por la identidad, pero el 0 es mucho más difícil de eliminar. Idealmente, nos gustaría usar algún teorema de recursión de Kleene, pero aún no lo he descubierto.S 0 0
fuente
Ahora, esta teoría es claramente completa en un sentido aproximado de @ cody, solo por la fuerza bruta; pero la afirmación es que también es consistente. Construyamos un modelo de ello.
Tenemos eso para todos los términos ,A Iv(A)∈U3 v A:B v⊨A:B Iv(A)∈Iv(B) Γ⊨A:B v v⊨x:C (x:C)∈Γ v⊨A:B
fuente