[Agda] termination by contradiction
Sergei Meshveliani
mechvel at botik.ru
Mon Jul 7 20:15:50 CEST 2014
On Mon, 2014-07-07 at 21:56 +0400, Sergei Meshveliani wrote:
> On Mon, 2014-07-07 at 18:11 +0200, Ulf Norell wrote:
> >
> > On Mon, Jul 7, 2014 at 2:36 PM, Sergei Meshveliani <mechvel at botik.ru>
> > wrote:
> >
> > I have installed Agda of July 7, 2014
> > (in which the checker loop is fixed), and tried this program
> > version:
> > ----------------------------------------------------------------
> > {-# NO_TERMINATION_CHECK #-}
> > findNatByContra :
> > (P : ℕ → Set) → (P? : Decidable P) → ¬ (∀ n → ¬ P n) → Σ ℕ P
> > findNatByContra P P? _ = findFrom 0
> > where
> > findFrom : ℕ → Σ ℕ P
> > findFrom n = case P? n of \ { (yes Pn) → (n , Pn)
> > ; (no _) → findFrom (suc n) }
> > [..]
>
> > I am trying to provide the feature ``classic termination
> > proof'' with
> > some possibilities in Agda.
> > [..]
> First of all, I got overruled on the behaviour of
> NO_TERMINATION_CHECK. I've implemented a new pragma NON_TERMINATING
> with the non-looping behaviour.
1) As I wrote before, the word `non-terminating' (algorithm Foo)
already has a default meaning:
``Foo does not terminate at each argument'',
or may be, ``Foo does not terminate at some argument''.
2) Is the word TERMINATES adequate?
(the meaning is ``postulate that it terminates'').
Regards,
------
Sergei
More information about the Agda
mailing list