¿Cuál es una explicación intuitiva de la correspondencia de Curry-Howard?

Answer 1

(Ver también: curry favor – Wikcionario)

Considere una fórmula de preposición (o teorema o conjetura) Y y un subconjunto X de {0,1} especificado por la siguiente regla:
[matemática] 0 \ en X [/ matemática] iff [matemática] Y [/ matemática] es verdadera.
[matemáticas] 1 \ en X [/ matemáticas] iff [matemáticas] Y [/ matemáticas] falso.
Que X no estará vacío ni habitado, por ejemplo, la hipótesis de Riemann
(valor de verdad desconocido para “indefinido” [matemáticas] \ en X [/ matemáticas]).
[math] X [/ math] es una prueba de [math] Y [/ math], en el sentido de que lo que habita (y si está habitado) nos dice si [math] Y [/ math] está probado, refutado o ninguno (por ejemplo, RH).

Por otro lado, podemos pensar en una función de tipo [math] \ tau_1 \ rightarrow \ tau_2 [/ math], como tomar una expresión [math] e_1 [/ math] de tipo [math] \ tau_1 [/ math] y produciendo algo [math] e_2 [/ math] de tipo [math] \ tau_2 [/ math], mientras se ejecuta . [math] e [/ math] de tipo [math] \ tau [/ math] puede tratarse como prueba ([math] X [/ math]) de la preposición ([math] Y [/ math]) y la función puede producir [matemática] X_2 [/ matemática] a partir de [matemática] X_1 [/ matemática], cambiando lo que está habitado, siempre que haya una [matemática] e [/ matemática] para [matemática] \ tau [/ matemática] (o hay una prueba [matemática] X [/ matemática] para el teorema [matemática] Y [/ matemática], en otras palabras ), es decir, [matemática] \ tau [/ matemática] es de tipo habitado.

Esa es la correspondencia de curry-Howard.

Tenga en cuenta que necesita saber “si hay una prueba (es [matemática] X [/ matemática] habitada), no cuál es la prueba real. Además, las pruebas en este contexto, son constructivas (por ejemplo, evidencia o testigo) más bien que por implicación.
Para [matemática] Y [/ matemática]: existen números irracionales [matemática] a, b [/ matemática] st [matemática] a ^ b [/ matemática] es racional.
[matemática] X [/ matemática] que dice, [matemática] Y [/ matemática] no es falsa, por lo tanto, [matemática] Y [/ matemática] es verdadera o dice [matemática] q [/ matemática] = algún valor (usted no sé racional o no), q es racional o irracional, [demuestre que] [matemáticas] Y [/ matemáticas] es cierto en cualquier caso, no es constructivo. Mientras que comenzando con algo como [matemáticas] a = \ sqrt 2, b = log_2 {9} [/ math] y mostrar que [math] a ^ b [/ math] es racional será una prueba constructiva ya que (a diferencia de la lógica clásica) no acepta el medio excluido (tampoco o no ) o doble negación (no falso significa verdadero)

Answer 2

La correspondencia de Curry-Howard es una correspondencia entre proposiciones y sus pruebas en algún sistema lógico, y valores y sus tipos en lenguajes de programación. En su forma más básica, la correspondencia es entre proposiciones y sus pruebas en una lógica mínima, y ​​los valores y sus tipos en el cálculo lambda simplemente tipado.

Si tomamos una función [math] f [/ math] de tipo [math] \ alpha \ rightarrow \ beta [/ math] en un lenguaje de programación funcional y la aplicamos a un valor [math] x [/ math] de tipo [ matemática] \ alpha [/ matemática], entonces el resultado [matemática] f [/ matemática] ([matemática] x [/ matemática]) será un valor de tipo [matemática] \ beta [/ matemática]. Esto a menudo se escribe como:

{[matemática] f [/ matemática]: [matemática] \ alpha \ rightarrow \ beta [/ matemática], [matemática] x [/ matemática]: [matemática] \ alfa [/ matemática]} [matemática] \ vdash [/ matemáticas] [matemáticas] fx [/ matemáticas]: [matemáticas] \ beta [/ matemáticas]

Si tuviéramos que eliminar los valores en lo anterior y mantener solo los tipos, entonces se leería:

{[matemáticas] \ alpha \ rightarrow \ beta [/ matemáticas], [matemáticas] \ alfa [/ matemáticas]} [matemáticas] \ vdash [/ matemáticas] [matemáticas] \ beta [/ matemáticas]

que es precisamente modus ponens en lógica mínima.

Esta correspondencia se puede ampliar a casi todos los conectivos lógicos en uso en lógica, incluyendo conjunción, disyunción, cuantificación universal y existencial y los operadores modales.

Lo que esto significa es que los lenguajes funcionales mecanografiados se pueden ver como cálculos para la construcción de prueba, y por el contrario, la construcción de prueba se puede considerar que tiene un significado computacional.

En Haskell se usa ampliamente para codificar las propiedades de un programa en los tipos de programa que, por correspondencia de Howard-Curry, significa que los programas de estos tipos codifican automáticamente pruebas de que los programas satisfacen las propiedades codificadas. Cuanto más rico es el sistema de tipos, más rica es la lógica. Puede ser un concepto muy poderoso en la construcción de programas.

Answer 3

No creo que haya una explicación particularmente intuitiva. La prueba matemática es rigurosa, no intuitiva. Supongo que lo más cerca que podrías estar sería decir que
1. Una función a probar debe tener un único propósito
2. Ese propósito se establece matemáticamente
3. Las entradas están definidas
3. Cada manipulación realizada en la función se evalúa matemáticamente (esto se vuelve bastante complicado para los bucles)
4. La salida se deriva y debe coincidir con el propósito de la función.

¿Qué tan intuitivo es eso? Depende, supongo.