Análisis de terminación

def  f ( n ):  mientras  n  >  1 :  si  n  %  2  ==  0 :  n  =  n  /  2  de lo contrario :  n  =  3  *  n  +  1

En informática , el análisis de terminación es un análisis de programas que intenta determinar si la evaluación de un programa determinado se detiene para cada entrada. Esto significa determinar si el programa de entrada calcula una función total .

Está estrechamente relacionado con el problema de la detención , que consiste en determinar si un programa dado se detiene para una entrada dada y cuál es indecidible . El análisis de terminación es incluso más difícil que el problema de la detención: el análisis de terminación en el modelo de máquinas de Turing como modelo de programas que implementan funciones computables tendría el objetivo de decidir si una máquina de Turing dada es una máquina de Turing total , y este problema está en el nivel de la jerarquía aritmética y, por lo tanto, es estrictamente más difícil que el problema de la detención.$Estilo de visualización: Pi _{2}^{0}}$

Ahora bien, como la cuestión de si una función computable es total no es semidecidible , ^[1] cada analizador de terminación de sonido (es decir, nunca se da una respuesta afirmativa para un programa que no termina) es incompleto , es decir, debe fallar en la determinación de la terminación para infinitos programas que terminan, ya sea ejecutándose para siempre o deteniéndose con una respuesta indefinida.

Una prueba de terminación es un tipo de prueba matemática que juega un papel crítico en la verificación formal porque la corrección total de un algoritmo depende de la terminación.

Un método simple y general para construir pruebas de terminación implica asociar una medida con cada paso de un algoritmo. La medida se toma del dominio de una relación bien fundada , como por ejemplo de los números ordinales . Si la medida "decrece" según la relación a lo largo de cada paso posible del algoritmo, debe terminar, porque no hay cadenas descendentes infinitas con respecto a una relación bien fundada.

Algunos tipos de análisis de terminación pueden generar o implicar automáticamente la existencia de una prueba de terminación.

Un ejemplo de una construcción de lenguaje de programación que puede o no terminar es un bucle , ya que se puede ejecutar repetidamente. Los bucles implementados mediante una variable de contador , como los que se encuentran normalmente en los algoritmos de procesamiento de datos , generalmente terminarán, como se demuestra en el siguiente ejemplo de pseudocódigo :

i := 0 bucle hasta que i = TAMAÑO_DE_DATOS process_data(data[i])) // procesar el fragmento de datos en la posición i i := i + 1 // pasar al siguiente fragmento de datos que se procesará

Si el valor de SIZE_OF_DATA no es negativo, es fijo y finito, el bucle eventualmente terminará, asumiendo que process_data también termina.

Se puede demostrar que algunos bucles siempre terminan o nunca terminan mediante una inspección humana. Por ejemplo, el siguiente bucle, en teoría, nunca se detendrá. Sin embargo, puede detenerse cuando se ejecuta en una máquina física debido a un desbordamiento aritmético : ya sea que genere una excepción o haga que el contador vuelva a un valor negativo y permita que se cumpla la condición del bucle.

i := 1 bucle hasta i = 0 yo := yo + 1

En el análisis de terminación también se puede intentar determinar el comportamiento de terminación de algún programa en función de una entrada desconocida. El siguiente ejemplo ilustra este problema.

i := 1 bucle hasta que i = DESCONOCIDO yo := yo + 1

Aquí la condición del bucle se define utilizando un valor UNKNOWN, donde el valor de UNKNOWN no ​​se conoce (por ejemplo, definido por la entrada del usuario cuando se ejecuta el programa). Aquí el análisis de terminación debe tener en cuenta todos los valores posibles de UNKNOWN y descubrir que en el posible caso de UNKNOWN = 0 (como en el ejemplo original) no se puede mostrar la terminación.

Sin embargo, no existe un procedimiento general para determinar si una expresión que implica instrucciones de bucle se detendrá, incluso cuando la inspección la realizan seres humanos. La razón teórica de esto es la indecidibilidad del problema de la detención: no puede existir un algoritmo que determine si un programa determinado se detiene después de un número finito de pasos de cálculo.

En la práctica, no se puede demostrar la terminación (o no terminación) porque cada algoritmo trabaja con un conjunto finito de métodos capaces de extraer información relevante de un programa determinado. Un método puede observar cómo cambian las variables con respecto a alguna condición de bucle (posiblemente mostrando la terminación para ese bucle), otros métodos pueden intentar transformar el cálculo del programa en alguna construcción matemática y trabajar sobre eso, posiblemente obteniendo información sobre el comportamiento de la terminación a partir de algunas propiedades de este modelo matemático. Pero como cada método solo puede "ver" algunas razones específicas para la (no) terminación, incluso a través de la combinación de tales métodos no se pueden cubrir todas las posibles razones para la (no) terminación. ^{[ cita requerida ]}

Las funciones recursivas y los bucles son equivalentes en expresión; cualquier expresión que involucre bucles se puede escribir utilizando recursión, y viceversa. Por lo tanto, la terminación de expresiones recursivas también es indecidible en general. Se puede demostrar que la mayoría de las expresiones recursivas que se encuentran en el uso común (es decir, no patológicas ) terminan a través de varios medios, generalmente dependiendo de la definición de la expresión misma. Como ejemplo, el argumento de la función en la expresión recursiva para la función factorial a continuación siempre disminuirá en 1; por la propiedad de buen orden de los números naturales , el argumento eventualmente alcanzará 1 y la recursión terminará.

función factorial (argumento como número natural) si argumento = 0 o argumento = 1 devuelve 1 en caso contrario  devuelve argumento * factorial(argumento - 1)

La comprobación de terminación es muy importante en lenguajes de programación de tipos dependientes y sistemas de demostración de teoremas como Coq y Agda . Estos sistemas utilizan el isomorfismo de Curry-Howard entre programas y pruebas. Las pruebas sobre tipos de datos definidos inductivamente se describían tradicionalmente utilizando principios de inducción. Sin embargo, más tarde se descubrió que describir un programa a través de una función definida recursivamente con coincidencia de patrones es una forma más natural de demostrar que usar principios de inducción directamente. Desafortunadamente, permitir definiciones no terminantes conduce a una inconsistencia lógica en las teorías de tipos ^{[ cita requerida ]} , por lo que Agda y Coq tienen comprobadores de terminación integrados.

Uno de los enfoques para la comprobación de terminación en lenguajes de programación con tipado dependiente son los tipos de tamaño. La idea principal es anotar los tipos sobre los que podemos realizar una recursión con anotaciones de tamaño y permitir llamadas recursivas solo en argumentos más pequeños. Los tipos de tamaño se implementan en Agda como una extensión sintáctica.

Existen varios equipos de investigación que trabajan en nuevos métodos que pueden mostrar la (no) terminación. Muchos investigadores incluyen estos métodos en programas ^[2] que intentan analizar el comportamiento de terminación automáticamente (es decir, sin interacción humana). Un aspecto en curso de la investigación es permitir que los métodos existentes se utilicen para analizar el comportamiento de terminación de programas escritos en lenguajes de programación del "mundo real". Para lenguajes declarativos como Haskell , Mercury y Prolog , existen muchos resultados ^{[3] [4] [5]} (principalmente debido a la sólida base matemática de estos lenguajes). La comunidad de investigación también trabaja en nuevos métodos para analizar el comportamiento de terminación de programas escritos en lenguajes imperativos como C y Java.

• Análisis de complejidad : el problema de estimar el tiempo necesario para finalizar
• Variante de bucle
• Programación funcional total : un paradigma de programación que restringe el rango de programas a aquellos que son demostrablemente terminales.
• Recursión de Walther

Los artículos de investigación sobre el análisis de la terminación automatizada de programas incluyen:

• Christoph Walther (1988). "Algoritmos limitados por argumentos como base para pruebas de terminación automatizadas". Actas de la 9.ª Conferencia sobre deducción automatizada . LNAI. Vol. 310. Springer. págs. 602–621.
• Christoph Walther (1991). "Sobre la demostración de la terminación de algoritmos por máquinas". Inteligencia artificial . 70 (1).
• Xi, Hongwei (1998). "Hacia pruebas de terminación automatizadas mediante congelamiento" (PDF) . En Tobias Nipkow (ed.). Rewriting Techniques and Applications , 9.ª conferencia internacional, RTA-98 . LNCS. Vol. 1379. Springer. págs. 271–285.
• Jürgen Giesl; Christoph Walther; Jürgen Brauburger (1998). "Análisis de terminación para programas funcionales". En W. Bibel; P. Schmitt (eds.). Deducción automatizada: una base para aplicaciones (posdata) . Vol. 3. Dordrecht: Kluwer Academic Publishers. págs. 135–164.
• Christoph Walther (2000). "Criterios para la terminación". En S. Hölldobler (ed.). Intellectics and Computational Logic (posdata) . Dordrecht: Kluwer Academic Publishers. pp. 361–386.
• Christoph Walther; Stephan Schweitzer (2005). "Análisis de terminación automatizado para programas incompletamente definidos" (PDF) . En Franz Baader; Andrei Voronkov (eds.). Actas de la 11.ª Conferencia Internacional sobre Lógica para Programación, Inteligencia Artificial y Razonamiento (LPAR) . LNAI. Vol. 3452. Springer. págs. 332–346.
• Adam Koprowski; Johannes Waldmann (2008). "Terminación ártica... por debajo de cero". En Andrei Voronkov (ed.). Técnicas de reescritura y aplicaciones, 19.ª conferencia internacional, RTA-08 (PDF) . Apuntes de clase en informática. Vol. 5117. Springer. págs. 202–216. ISBN. 978-3-540-70588-8.

Las descripciones del sistema de herramientas de análisis de terminación automatizada incluyen:

• Giesl, J. (1995). "Generación de ordenamientos polinomiales para pruebas de terminación (descripción del sistema)". En Hsiang, Jieh (ed.). Rewriting Techniques and Applications, 6th Int. Conf., RTA-95 (posdata) . LNCS. Vol. 914. Springer. págs. 426–431.
• Ohlebusch, E.; Claves, C.; Marché, C. (2000). "TALP: una herramienta para el análisis de terminación de programas lógicos (descripción del sistema)". En Bachmair, Leo (ed.). Rewriting Techniques and Applications, 11th Int. Conf., RTA-00 (posdata comprimida) . LNCS. Vol. 1833. Springer. págs. 270–273.
• Hirokawa, N.; Middeldorp, A. (2003). "Herramienta de terminación Tsukuba (descripción del sistema)". En Nieuwenhuis, R. (ed.). Técnicas de reescritura y aplicaciones, 14.ª conferencia internacional, RTA-03 (PDF) . LNCS. Vol. 2706. Springer. págs. 311–320.
• Giesl, J.; Thiemann, R.; Schneider-Kamp, P.; Falke, S. (2004). "Pruebas de terminación automatizadas con AProVE (descripción del sistema)". En van Oostrom, V. (ed.). Rewriting Techniques and Applications, 15th Int. Conf., RTA-04 (PDF) . LNCS. Vol. 3091. Springer. págs. 210–220. ISBN. 3-540-22153-0.
• Hirokawa, N.; Middeldorp, A. (2005). "Tyrolean Termination Tool (system description)". En Giesl, J. (ed.). Term Rewriting and Applications, 16th Int. Conf., RTA-05 . LNCS. Vol. 3467. Springer. págs. 175–184. ISBN. 978-3-540-25596-3.
• Koprowski, A. (2006). "TPA: Terminación probada automáticamente (descripción del sistema)". En Pfenning, F. (ed.). Term Rewriting and Applications, 17.ª conferencia internacional, RTA-06 . LNCS. Vol. 4098. Springer. págs. 257–266.
• Marché, C.; Zantema, H. (2007). "La competencia de terminación (descripción del sistema)". En Baader, F. (ed.). Term Rewriting and Applications, 18th Int. Conf., RTA-07 (PDF) . LNCS. Vol. 4533. Springer. págs. 303–313.

• Análisis de terminación de programas funcionales de orden superior
• Lista de correo de herramientas de terminación
• Concurso de terminación: véase Marché, Zantema (2007) para una descripción
• Portal de terminación