[Agda] termination by contradiction

Sergei Meshveliani mechvel at botik.ru
Mon Jun 30 11:52:28 CEST 2014


People,

is it possible in Agda to prove termination of a function by programming
a 
      negation of non-termination             -- call it  method  (M)

(deriving an absurd from assuming an infinite work of the algorithm)
?

A.A.Markov wrote that this provides a wider class of constructive
objects, and that this is intuitive enough.

My current termination proofs in Agda use only a simple approach by
providing an upper bound for a certain counter. And I have an impression
that (M) gives something wider.

Consider the following attempt.
For a recursive function        f : Nat -> Nat,  
define  
       g : Nat -> Nat -> State,  

such that   g x n  is the `state' of the computation of  f x  
at the step  n.
Then the type
              (n : Nat) ->  \neg (isFinalState (g x n))          (NT)

expresses a non-termination at x, and      

          ((n : Nat) ->  \neg (isFinalState (g x n)))  ->  \bottom

will express termination by (M).
Right?

How to express this in Agda ?  Needs it to be expressed?

Thanks,

------
Sergei



More information about the Agda mailing list