[Agda] termination proofs
Serge D. Mechveliani
mechvel at botik.ru
Tue Sep 25 17:59:09 CEST 2012
On Mon, Sep 24, 2012 at 08:33:58PM +0100, Peter Hancock wrote:
> On 24/09/2012 19:01, Serge D. Mechveliani wrote:
>
>> Does there exist an algorithmic map in Nat -> Nat for which there
>> is not any Agda program with a termination proof accepted by Agda ?
> [..]
>
> On countability grounds too, there are uncountably many functions in
> Nat -> Nat,
> but since Agda is a formal system (isn't it?) there are only countably many
> expressions in it of (formal) type Nat -> Nat. (They are not just countable
> but even computably enumerable.)
> [..]
The countability grounds is not relevant here, because I asked about an
_algorithmic_ map in Nat -> Nat.
An algorithm here can be put as
any terminating Agda function (program) f : Nat -> Nat
which is applied without the termination check.
But in all the rest -- I see, thanks to peopleя. The imression is that
the set of provably-terminating Agda programs is large enough.
Regards,
------
Sergei
More information about the Agda
mailing list