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
- Teaching computability theory with machine-checked proofs
- Extending the library with new undecidability reductions
- Research in synthetic computability and formal logic
- Comparing undecidability proofs across different computational models
- Building upon established reductions for new problems
Not Ideal For
- Projects needing quick, informal proof sketches for teaching or brainstorming without formal verification overhead
- Applications requiring executable decision procedures or practical algorithms for specific computational problems
- Teams unfamiliar with Coq or formal proof assistants, seeking plug-and-play solutions for software development
- Research environments using proof assistants other than Coq, such as Isabelle or Agda, without Coq integration
Pros & Cons
Pros
Defines undecidability relative to the enumerability of the complement of the Turing machine halting problem in Coq, providing a rigorous, type-theoretic approach as detailed in the synthetic definitions.
Includes seed problems like Turing machine halting and Post correspondence, advanced problems from first-order logic to lambda calculus, and target problems for reductions, covering a wide range of undecidability results.
All proofs are fully formalized and checked by Coq, ensuring accuracy and reliability, as emphasized in the library's description and CI badge.
Designed for contributions with guidelines for adding new proofs, making it a living resource for the community, as invited in the README's contribution section.
Cons
Requires Coq 8.20 and MetaCoq, with compatibility issues across branches and older Coq versions, as noted in the troubleshooting section, limiting flexibility.
Setup involves opam switches, specific OCaml versions (e.g., 4.14.1+flambda), and manual steps, which can be cumbersome and error-prone for newcomers.
Assumes proficiency in Coq and formal verification, with no beginner-friendly tutorials or simplified examples, making it inaccessible without prior expertise.
Frequently Asked Questions
Related Projects
Interaction TreesA Library for Representing Recursive and Impure Programs in Coq
coq-haskellA library for formalizing Haskell types and functions in Coq
ExtLibA library of Coq definitions, theorems, and tactics. [maintainers=@gmalecha,@liyishuai]
MetalibThe Penn Locally Nameless Metatheory Library
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.