Formalised Undecidable Problems
A Coq library containing mechanized reductions to establish undecidability results for problems in logic and computation.
What is Formalised Undecidable Problems?
The Coq Library of Undecidability Proofs is a formal, machine-checked collection of reductions that prove various problems in logic and computation are undecidable. It uses a synthetic approach within the Coq proof assistant to establish undecidability by showing that decidability of a problem would imply the enumerability of the complement of the Turing machine halting problem. The library serves as a rigorous framework for verifying classical undecidability results.
Researchers and practitioners in formal verification, logic, and theoretical computer science who need to formally verify undecidability proofs or extend the library with new results. It is also suitable for educators teaching computability theory with a formal methods perspective.
It provides a comprehensive, collaborative, and extensible library of fully mechanized undecidability proofs, ensuring correctness through Coq's proof checking. The synthetic approach offers a foundational perspective distinct from traditional pen-and-paper proofs.
Overview
A library of mechanised undecidability proofs in the Coq proof assistant.
Use Cases
Best For
- Formally verifying undecidability results in Coq
Related Projects
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
