Si desea estudiar las propiedades de terminación en profundidad, los programas que utilizan sucesor-aritmética son un objeto de estudio ideal: Usted sabe a priori lo que deben describir, por lo que puede concentrarse en los detalles más técnicos. Usted tendrá que entender varias nociones.

Terminación universal

La forma más fácil de explicarlo, es considerar Goal, false. Esto termina iff Goal termina universalmente. Es decir: Mirar trazadores es el más ineficaz way-te mostrarán una única ruta de ejecución. ¡Pero tienes que entenderlos todos a la vez! Además, nunca mires las respuestas cuando quieres una terminación universal, solo te distraerán. Usted lo ha visto arriba: Usted consiguió tres respuestas ordenadas y correctas, solamente entonces sus bucles del programa. Así que mejor" desactivar " respuestas con false. Esto elimina toda distracción.

Corte de falla

La siguiente noción que necesita es la de un corte de falla . Tome una lógica monótona pura programa y lanza algunos goles false. Si el segmento de falla resultante no termina (universalmente), tampoco lo hará el programa original. En su ejemplo, considere:

prod(0,M,0) :- false.
prod(s(N), M, P) :-
    prod(N,M,K), false,
    sum(K,M,P).

Estos objetivos false ayudan a eliminar adornos irrelevantes en su programa: La parte restante le muestra claramente, por qué prod(X,Y,s(s(s(s(s(s(0))))))). no termina. ¡No termina, porque a ese fragmento no le importa P en absoluto! Usted está esperando que el tercer argumento ayudará a hacer prod/3 terminar, pero el fragmento te muestra que todo es en vano, ya que P no ocurre en ninguna meta. No hay necesidad de rastreadores parlanchines.

A menudo no es tan fácil encontrar cortes de falla mínimos. Pero una vez que encontró uno, es casi trivial determinar sus propiedades de terminación o más bien no terminación. Después de algún tiempo puedes usar tu intuición para imaginar una rebanada, y luego puedes usar tu razón para verificar si esa rebanada es relevante o no.

Lo que es tan notable sobre la noción de un corte de falla es esto: Si desea mejorar el programa, tiene que modificar su programa en la parte visible en el fragmento anterior! Mientras no lo cambies, el problema persistirá. Por lo tanto, un corte de falla es una parte muy relevante de su programa.

Inferencia de terminación

Eso es lo último que necesita: Un inferencer (o analizador) de terminación como cTI le ayudará a identificar la condición de terminación rápidamente. Mira las condiciones de terminación inferidas de prod/3 y la mejora prod2/3 aquí!

Editar: Y ya que esta era una pregunta de tarea no he publicado la solución final. Pero para dejarlo claro, aquí están las condiciones de terminación obtenidas hasta ahora:

    prod(A,B,C)terminates_if b(A),b(B).
    prod2(A,B,C)terminates_if b(A),b(B);b(A),b(C).

Así que el nuevo prod2/3 es estrictamente mejor que el programa original!

Ahora, depende de usted encontrar el programa final. Su condición de terminación es:

   prod3(A,B,C)terminates_if b(A),b(B);b(C).

Para empezar, trate de encontrar el segmento de falla para prod2(A,B,s(s(s(s(s(s(0)))))))! Esperamos que terminar, pero todavía no lo hace. Así que tome el programa y añadir manualmente false objetivos! La parte restante le mostrará la clave!

Como sugerencia final: Necesitas agregar un objetivo extra y un hecho.

Editar: A petición, aquí está el segmento de falla para prod2(A,B,s(s(s(s(s(s(0))))))):

prod2(0,_,0) :- false.
prod2(s(N), M, P) :-
   sum(M, K, P),
   prod2(N,M,K), false.

sum(0, M, M).
sum(s(N), M, s(K)) :- false,
    sum(N,M,K).

Tenga en cuenta la definición significativamente simplificada de sum/3. Sólo dice: 0 más cualquier cosa es cualquier cosa. No más. Como consecuencia, incluso los más especializados prod2(A,0,s(s(s(s(s(s(0))))))) se repetirán mientras queprod2(0,X,Y) elegantemente termina ...