Programación y

Question

Supongamos que tengo un sencillo programa que implementa un algoritmo (dicen búsqueda en profundidad), escrito en un simple imperativo lenguaje de programación con el estándar para los bucles, las repeticiones, las sentencias condicionales y así sucesivamente. Se toma en un bien de entrada especificado y tiene una salida especificada.

Supongamos que quiero verificar que siempre produce la salida correcta para cada entrada. Puedo tratar el programa como un objeto matemático sujeto a ciertas reglas del lenguaje de programación. Escribo formal de una prueba matemática, suponiendo que el habitual de los axiomas de ZFC y la lógica de primer orden, para demostrar que esto es cierto.

Cómo iba yo a saber que mi programa definitivamente las obras (es decir, para todas las variables de entrada, de salida correctamente) debido a esta prueba? Hago saber que en el sistema de axiomas ZFC, mi programa de obras, ya que se define al trabajo (que es deducible formalmente). Sin embargo, parece que la corrección de mi programa no requiere que el pleno de la maquinaria de ZFC; su única axiomas son las reglas del lenguaje de programación. Comúnmente se utiliza la prueba de técnicas como la inducción matemática se fundamenta en los axiomas de ZFC, pero no sabemos todavía que estos sostener debido solamente a las reglas del lenguaje de programación.

Es posible que mi programa no funciona, sino que está demostrado que funciona en ZFC? Si ese es el caso, ¿por qué todos los algoritmos probados en el marco habitual de ZFC (suponiendo que todos los axiomas de la teoría de conjuntos y la lógica de primer orden)?

EDITAR: Puede la verificación formal de programas (con 100% de seguridad de acuerdo a las especificaciones del lenguaje de programación) se realiza en ZFC? Estoy asumiendo que se puede hacer en virtud del axioma débil de los sistemas (por ejemplo, la lógica de Hoare)?

Answer 1

Depende de lo que quieres decir por "trabajo".

Si lo que desea es mostrar que un programa nunca exhibe algunas simples de comportamiento - por ejemplo, si desea mostrar no halt - entonces, si ZFC demuestra este hecho, es correcto, siempre que ZFC es consistente.

Si desea mostrar que un programa va en algún punto se presentan algunos simples de comportamiento - por ejemplo, si desea mostrar se va a detener - y después de conocer la exactitud de un ZFC-prueba requiere un poco más que la suposición de que ZFC es consistente - necesitamos saber que el es $\Sigma^0_1$-sonido. Esta es una técnica hipótesis mucho más débil que la suposición de que "Cada aritmética consecuencia de ZFC es verdadero" (la cual por lo general suponemos).

Y, por supuesto, el teorema de Gödel muestra que ZFC no siempre será suficiente, incluso para el más simple de las declaraciones - hay una máquina de Turing $T$ que nunca se detiene (suponiendo que ZFC es consistente), pero que ZFC no puede resultar nunca se detiene (de nuevo, suponiendo que ZFC es consistente).

---

Pero estos son problemas generales con los que vas a tener con cualquier fondo de la teoría, no sólo de ZFC. Cada resultado de este tipo - en realidad, cada resultado en todas existe en el contexto de suposiciones de fondo. ZFC pasa a ocupar ese punto dulce de (a) siendo muy común para asumir, (b) razonablemente bien entendida, y (c) lo suficientemente potente como para manejar casi todos los "razonable" de los problemas. (Uno puede intentar hacer más fuertes argumentos para ZFC frente a otras teorías, pero eso es un problema para otro momento.) Así que la respuesta a por qué usamos ZFC: bueno, tenemos que usar algo. :)

Answer 2

Veamos esto de una manera mucho más el punto de vista matemático.

Un algoritmo es como una teoría de la $T$ en algunos lógica de primer orden. Y se puede preguntar si la teoría de la prueba $\varphi$. Y esto puede comprobarse en la sintaxis o en otras formas. Y eso está bien.

Una aplicación es como un modelo de $T$. Así que ahora en vez de preguntar si $T$ demuestra $\varphi$ te están preguntando si $\varphi$ es verdadera en el modelo de $M$. Este resulta ser equivalente a la pregunta de si la teoría de la $M$ demuestra $\varphi$, y eso es importante. Porque significa que podemos saltar entre las dos preguntas acerca de la verdad y provability.

Si su aplicación (incluyendo el compilador y el procesador y otras cosas) es fiel y no se desvía del algoritmo (y esto significa que usted tiene que ignorar completamente, todas las limitaciones físicas o empuje en el algoritmo de alguna manera), entonces el hecho de que se demostró que el algoritmo funciona significa que su aplicación funciona.

Si su aplicación no es fiel a continuación, usted está preguntando si el algoritmo que se aplica fielmente es equivalente al algoritmo que se quería implantar. Eso es otra cuestión, y depende también de su capacidad para extraer el verdadero "algoritmo" de su aplicación.