On proving the termination of algorithms by machine

摘要

Proving the termination of a recursively defined algorithm requires a certain creativity of the (human or automated) reasoner for inventing a hypothesis whose truth implies that the algorithm terminates. We present a reasoning method for simulating this kind of creativity by machine. The proposed method works automatically, i.e. without any human support. We show, (1) how a termination hypothesis for an algorithm is synthesized by machine, (2) which knowledge about algorithms is required for an automated synthesis, and (3) how this knowledge is computed. Our method solves the problem for a relevant class of algorithms, including classical sorting algorithms and algorithms for standard arithmetical operations, which are given in a pure functional notation. The soundness of the method is proved and several examples are presented for illustrating the performance of the proposal. The method has been implemented and proved successful in practice.