[Agda] termination proofs

Peter Hancock hancock at spamcop.net
Tue Sep 25 18:12:01 CEST 2012


> The countability grounds is not relevant here, because I asked about an
> _algorithmic_ map in  Nat -> Nat.

For me, a function just *is* an algorithmic map which we can recognise as total.
The normal Cantor diagonalisation argument shows that Nat->Nat is uncountable.

I admit, this will seem strange at first, because there are only countably
many Turing machines, and the total ones will be a subset of these.  But
the notion of a cardinal is a bit strange constructively.  There are
arbitrarily many subsets of a singleton, constructively.  I suggest that
this argument is worth a bit more of your attention.

(I also admit I am sweeping some subtle points under the carpet.)

Regards,

Peter


More information about the Agda mailing list