¿Prueba si una prueba arbitraria es circular?

13

Estaba pensando en pruebas y me encontré con una observación interesante. Por lo tanto, las pruebas son equivalentes a los programas a través del isomorfismo de Curry-Howard, y las pruebas circulares corresponden a una recursión infinita. Pero sabemos por el problema de detención que, en general, es indecidible probar si un programa arbitrario se repite para siempre. Por Curry-Howard, ¿eso significa que no hay un "comprobador de pruebas" que pueda determinar si una prueba usa razonamiento circular?

Siempre he pensado que se supone que las pruebas están compuestas por pasos fáciles de verificar (que corresponden a las aplicaciones de las reglas de inferencia), y verificar todos los pasos le da la confianza de que la conclusión sigue. Pero ahora me pregunto: ¿tal vez es realmente imposible escribir un comprobador de pruebas de este tipo, porque no hay forma de evitar el problema de detención y detectar el razonamiento circular?

logic curry-howard hewasonlyacat
fuente

Respuestas:

15

La gran mayoría de los sistemas de prueba no permiten pruebas circulares infinitas, pero lo hacen al hacer que sus idiomas no sean completos de Turing.

Y∀un.(un→un)→un

ununun

La clave aquí es que el combinador Y está integrado en un lenguaje, se toma como un axioma. Entonces, si desea que no le cause problemas, ¡deshágase de él como un axioma!

La mayoría de los sistemas de prueba formales, debido a esto, requieren que su recursión esté bien fundada. Solo aceptan funciones que pueden demostrar que se detendrán. Y como resultado, rechazan algunos programas que se detienen, pero que no pueden probar.

Coq hace esto de una manera bastante limitada: solo requiere que cualquier función recursiva tenga un argumento donde cualquier llamada recursiva solo use versiones estrictamente más pequeñas de ese argumento. Agda hace algo similar, pero con una comprobación un poco más sofisticada para aceptar algunos programas más.

jmite
fuente
1
¿Coq descarta algunos teoremas legítimos que de otro modo podría probar? ¿O siempre hay soluciones para cuando el verificador de totalidad es demasiado conservador? (Supongo que la respuesta es la misma para otros asistentes de pruebas basados ​​en la teoría del tipo dependiente)
Estufa
1
@boyers FWIW, en Coq uno puede usar Functiono Program Fixpointconstrucciones para probar que alguna función es total si falla el verificador de totalidad. Un ejemplo simple es la función merge-sort en las listas. Es necesario probar manualmente que dividimos las listas (de longitud> 1) en sublistas estrictamente más pequeñas.
Anton Trunov
@boyers Sí, tiene que haber cosas que no puedes probar en Coq, según el primer teorema de Gödel. En la práctica, es raro encontrarlos, pero siempre existe el argumento diagonal: Coq no puede probar Coq por sí mismo, solo puede probar un subconjunto (un subconjunto muy grande, mente, que incluye todas las características pero con un límite inferior de cuánta recursividad puede manejar). Recuerdo haber leído que la teoría de Coq es equivalente a los axiomas de Peano más la existencia de un cierto ordinal grande (y, por lo tanto, las pruebas que suponen que un ordinal aún más grande no puede caber), pero no puedo encontrar la referencia ahora.
Gilles 'SO- deja de ser malvado'
@AntonTrunov En este contexto, Programy similares son una pista falsa. No cambian la teoría. Lo que hacen es azúcar sintáctico para usar una medida en una prueba: en lugar de razonar que el objeto que le interesa se hace más pequeño, agrega un nivel de indirección: calcule que algún otro objeto se hace más pequeño (por ejemplo, algún tamaño) y demuestre que se hace más pequeño Ver la Wfbiblioteca
Gilles 'SO- deja de ser malvado'
@Gilles Asumí que el contexto era sobre el lado práctico (concreto), como cuando falla la heurística de Coq ... ¿Podría intentar encontrar el documento que mencionó? Un enlace sería muy apreciado.
Anton Trunov