Soy relativamente nuevo en teoría de tipos y programación dependiente. He estado estudiando el cálculo de construcciones (CoC) y otros sistemas de tipo puro. Estoy particularmente interesado en usarlo como una representación intermedia de preservación de pruebas para un sistema compilador.
Entiendo que los tipos (co) recursivos son representables , computacionalmente , usando como el único constructor de tipos. Sin embargo, he leído que no se pueden usar para crear pruebas por inducción (¡perdóname, no puedo encontrar dónde ahora!), Por ejemplo, que no podría probar que en CoC simple (aunque se puede escribir como ).0 ≠ 1 Nat Π ( N : ∗ ) . Π ( S : N → N ) . Π ( Z : N ) . norte
Supongo que es por eso que construyeron el cálculo de las construcciones inductivas (CIC). ¿Es esto correcto? ¿Pero por qué? No pude encontrar ningún material que explicara por qué tales pruebas no se pueden representar sin usar tipos (co) inductivos como primitivos. Si esto no es cierto, ¿por qué agregarlos como primitivos en CIC?
fuente