Proof assistants such as Agda can be used to assert properties about programs, such as the double of a number is even. Interestingly, supercompilers can be used for the same purpose, creating typeless proofs. Even more interestingly, macro tree transducers can, too. My question is: what is the relationship between those? What does a dependently typed language have that makes it more powerful than other type systems as far as theorem proving goes, considering proofs can be done without types?
Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same?
type theory;functional programming;dependent types;proof assistants