Questions: Interactive Theorem Proving

Question 1

What distinguishes a machine-checked proof in Coq from an informal mathematical proof?

• A. Machine-checked proofs are shorter and easier to read
• B. Every logical step is verified by a small trusted kernel, making the proof's correctness independent of the user's reasoning ability. Informal proofs rely on the reader's judgment to assess whether each step is valid
• C. Machine-checked proofs can prove statements that informal proofs cannot
• D. Machine-checked proofs are generated automatically without human input

Answer: (B)

The key property is the trusted kernel: the proof assistant has a small core type-checker (a few thousand lines) that validates every proof step. The user can make mistakes, use dubious heuristics, or employ powerful automation — but the kernel will only accept the proof if every step is logically justified. This gives much stronger assurance than informal proofs, where a single oversight in a complex argument can invalidate the entire proof. The tradeoff is the effort to formalize: machine-checked proofs are typically 5-20x longer than informal ones.

Question 2

The CompCert verified C compiler guarantees that the compiled machine code has the same observable behavior as the source C program. This was proven using which proof assistant?

• A. Lean
• B. Coq
• C. Isabelle/HOL
• D. Agda

Answer: (B)

CompCert, developed by Xavier Leroy, is a C compiler where every optimization pass is formally verified in Coq to preserve program semantics. The machine-checked proof guarantees that any behavior of the compiled code is a valid behavior of the source program — miscompilation bugs are impossible (within the modeled subset of C). This is a landmark achievement in formal methods: a production-quality compiler with end-to-end correctness guarantees.

Question 3

Why do proof assistants use a small trusted kernel rather than trusting the entire tool, and what is the practical implication of this design?

Model answer: The kernel is the only code that needs to be correct for the proofs to be valid. A small kernel (typically a few thousand lines) can be audited, tested, and formally analyzed. The rest of the proof assistant — tactics, automation, user interface, libraries — can be arbitrarily complex because anything they produce is re-checked by the kernel. If a tactic generates a wrong proof step, the kernel rejects it. This design, called the 'de Bruijn criterion,' minimizes the trusted computing base.

This is analogous to the principle of least privilege in security. By concentrating trust in a small, well-understood component, the overall system achieves high assurance despite its complexity. Coq's kernel is about 10,000 lines of OCaml. All of Coq's sophisticated tactic language, automation, and standard library depend on this kernel for soundness. If the kernel has no bugs (and it has been very thoroughly tested), then every proof Coq accepts is valid.

Question 4

Interactive theorem proving cannot be fully automated for interesting theorems because the underlying logic is undecidable.

• T. True
• F. False

Answer: True

Proof assistants typically use logics (higher-order logic, dependent type theory) in which validity is undecidable — there is no algorithm that can determine whether an arbitrary statement is provable. This is why the process is 'interactive': the human provides the creative insights (proof strategy, key lemmas, case splits) and the machine verifies each step. Automation (SAT/SMT solvers, decision procedures, proof search tactics) handles routine obligations, but non-trivial theorems require human guidance. The division of labor — human creativity, machine rigor — is the essence of interactive theorem proving.