[Agda] strange termination check
Sergei Meshveliani
mechvel at botik.ru
Sat Oct 12 12:17:43 CEST 2013
On Sat, 2013-10-12 at 13:42 +0400, Sergei Meshveliani wrote:
> On Sat, 2013-10-12 at 14:33 +0900, Andreas Abel wrote:
> > Unfortunately, the termination-depth-trick works only for natural
> > numbers and sizes, not for lists and other data structures with a
> > constructor that has more than one argument.
> >
>
> The consequence is that one does not know how to provide termination
> without complications brought with inductive types.
> For example, I tried to replace in the below example the step
> (b ∷ b' ∷ bs) --> b' ∷ bs
>
> with one-level step, by denoting b'' = b' :: bs ...
> And failed.
>
> Is this difficult (if correct) to implement in Agda, say,
> "termination by a proper subterm" ?
But if it is by the checker, then this is a hidden termination proof.
And when it is by an inductive type, it is (probably) a proof given as
an Agda data
(it this so?).
May be it has sense to provide an option like
--use-termination-proof-by-subterm
Regards,
------
Sergei
More information about the Agda
mailing list