Terminación de un algoritmo

Definición

Propiedad por la que un algoritmo finaliza después de un número finito de pasos para toda entrada permitida.

Intuición

No basta con que el procedimiento produzca una respuesta si llega al final: también hay que descartar ejecuciones infinitas.

Formulación

$$\forall x\in I,\exists t<\infty \text{ tal que la ejecucioˊn de }A(x)\text{ se detiene en }t.$$

Ejemplo mínimo

La búsqueda lineal termina porque su ciclo examina como máximo las $n$ posiciones del arreglo.

Contraejemplo o límites

Un ciclo cuyo progreso no está acotado ni se justifica con una medida decreciente puede no terminar.

Relaciones

• Junto con: Validez de un algoritmo.
• Se utiliza en: demostraciones de corrección total.
• Contrasta con: Problema de la parada, que limita la verificación automática de esta propiedad en general.

Procedencia

• Clase: Introducción al curso
• Fuente: presentación introductoria, diapositivas 11–13.