agda / agda

Agda is a dependently typed programming language / interactive theorem prover.
https://wiki.portal.chalmers.se/agda/pmwiki.php
Other
2.39k stars 337 forks source link

TBT accepts non-terminating function that makes Agda loop in the injectivity checker #7272

Open andreasabel opened 2 weeks ago

andreasabel commented 2 weeks ago

Agda seems to loop on this example:

{-# OPTIONS --type-based-termination #-}

data ⊥ : Set where

data T (A : Set) : Set where
  sup : (A → T A) → T A

variable A : Set

sup' : (A → T A) → T A
sup' f = f' where f' = sup f

g : T A → ⊥
g (sup f) = g (sup' f)

@ATTN: @knisht

Agda hanging itself here is quite unfair, since I was so close to proving absurdity:

Type-based termination succeded for definitions [g]

e : T ⊥
e = sup λ()

false : ⊥
false = g e

It seems that Agda hangs in the injectivity checker when trying to reduce g.