¿Por qué es tan difícil de traducir algunos demuestra en forma legible por máquina?

Question

Acabo de leer un tema en mathoverflow sobre el hombre contra la máquina en matemáticas. El tema fue inspirado por la reciente victoria de Alfa Ir por el Mundo Vaya Campeón, Lee Sedol. Me recordó un artículo que he leído (posiblemente en el American Mathematical Monthly) acerca de la traducción de la Curva de Jordan Teorema en la máquina-seleccionable forma.

Me encantaría oír acerca de por qué es tan difícil, en general, para traducir una prueba de algunos teorema de modo que una máquina puede comprobar. Lo que es fundamentalmente diferente entre, dice, el Teorema de los Cuatro Colores y Jordania Curva Teorema que hace que sea mucho más difícil para la máquina de lidiar con el futuro?

EDIT: he encontrado un maravilloso enlace relacionado ¿por Qué es difícil demostrar Jordania Curva Teorema en el caso de copo de nieve de Koch.

Answer 1

Otro ejemplo es Gonthier de la reciente prueba de Feit–Thompson teorema. Sería demasiado tiempo para responder a su pregunta en detalle, pero en este enlace (en francés) COQ ET CARACTÈRES, Preuve formelle du théorème de Feit et Thompson, contiene varias referencias pertinentes.

En particular, Una Edición Especial sobre la Prueba Formal de los Avisos de la AMS reúne cuatro artículos:

La Prueba Formal por Thomas Hales

La Prueba Formal de-Cuatro-Color Teorema de Georges Gonthier

La Prueba Formal--la Teoría y la Práctica por John Harrison

La Prueba Formal--introducción por Freek Wiedijk

Answer 2

No es mucho más difícil de lo mucho más tedioso. En una prueba formal (uno legible por un programa de ordenador), cada paso en la solución de una ecuación debe ser explícita. Usted no puede asumir, por ejemplo, que el lector (un equipo en este caso) sabe que la adición de los números reales es conmutativa. Usted no puede incluso decir, por la conmutatividad de la suma, tal y tal. Explícitamente, debe citar algunos teorema demostrado anteriormente de la forma $$\forall x: \forall y:[x\in \mathbb{R} \land y \in \mathbb{R} \implies x+y=y+x]$$ A continuación, debe especificar una expresión para ambas variables vinculadas $x$ cualquier $y$. Entonces usted debe probar cada expresión es de hecho un número real. A continuación, debe aplicar el desprendimiento de la regla. (Dejando de lado algunos detalles!) A continuación, debe seleccionar de forma explícita las expresiones en la fórmula original de la que desea hacer la sustitución. ¡Uf!

Lo que normalmente es simplemente "conocido" y se aplica a casi subconciously por un experimentado lector humano para llenar los huecos, es un proceso de múltiples pasos en una prueba formal. La ventaja, por supuesto, es que usted puede estar prácticamente seguro de que no ha habido errores. Para fines prácticos, no habría ninguna necesidad real para cualquier verificación por parte de una persona experta.