[Agda] termination proof problem
Sergei Meshveliani
mechvel at botik.ru
Tue Mar 29 12:30:56 CEST 2016
On Tue, 2016-03-29 at 10:21 +0200, Ulf Norell wrote:
> A trick you can use is to skip checking the bound until after a finite
> (but possibly large) number of steps. Basically you write a fast
> search that takes a counter starting at a billion (say) that ignores
> the bound and only when that counter reaches zero do you switch to the
> slow search where you check the bound. For your example:
>
>
> https://gist.github.com/UlfNorell/f2d8674b1d6b98172827
> [..]
>
This looks reasonable. Thank you.
I wonder of whether there is possible a perfect way out.
I have the following question.
1) `search' has a proved bound (bound n) and the counter cnt that
starts at 1 + (bound n), moves towards zero, and it is proved in
the program that it never turns zero (say, the pattern
(search ... zero =) has \bottom-elim in RHS, so that `search' stops
earlier).
2) The checker has checked termination by seeing these expressions for
cnt.
After this, it is clear that cnt is not needed in the program.
It can be rewritten with removing the counter and adding
{-# TERMINATING #-}, so that the two algorithms are equivalent.
Right?
Is it possible to introduce some special language construct for
"termination by counter", so that the checker could do this
transformation automatically, in a general and safe way?
Thanks,
------
Sergei
More information about the Agda
mailing list