Reproduce “On the Expressive Power of Schemes” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Gilles Dowek, Ying Jiang
Researchers from INRIA and the Chinese Academy of Sciences developed the scheme-calculus, a formal system for natural deduction proofs that uses type-based canonical variables instead of explicit names for hypotheses. A dependently-typed version of this calculus, despite its inherent non-determinism, expresses all functions provably total in impredicative arithmetic (HA2), matching the expressive power of the dependently-typed lambda calculus and providing a context-free language of proofs for minimal propositional logic.
Key insights
- The elimination of explicit hypothesis names results in an inherently non-deterministic reduction process in the scheme-calculus, as canonical variables can refer to multiple abstractions of the same type.
- Despite non-determinism and the general simply-typed version not being strongly normalizing, the dependently-typed scheme-calculus (DTSC) rigorously maintains the subject-reduction property, ensuring the logical soundness of the calculus.
- By restricting to a minimal substitution strategy and weak reduction, the DTSC achieves weak normalization, guaranteeing that every well-typed scheme can be reduced to a weak head normal form, sufficient for computational content extraction.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.