We formalise the computational undecidability of validity, satisfiability, and provability of first-
order formulas following a synthetic approach based on the computation native to Coq's …

We give a formalised and machine-checked account of computability theory in the Calculus
of Inductive Constructions (CIC), the constructive type theory underlying the Coq proof …

We formally prove the undecidability of entailment in intuitionistic linear logic in Coq. We
reduce the Post correspondence problem (PCP) via binary stack machines and Minsky …

We present a framework for the verified programming of multi-tape Turing machines in Coq.
Improving on prior work by Asperti and Ricciotti in Matita, we implement multiple layers of …

We present an extension to the $\mathtt {mathlib} $ library of the Lean theorem prover
formalizing the foundations of computability theory. We use primitive recursive functions and …

We formalise undecidability results concerning higher-order unification in the simply-typed λ-
calculus with β-conversion in Coq. We prove the undecidability of general higher-order …

Rewriting is a framework for reasoning about functional programming. The dependency pair
criterion is a well-known mechanism to analyze termination of term rewriting systems …

This paper presents a formalization of several termination criteria for first-order recursive
functions. The formalization, which is developed in the Prototype Verification System (PVS) …

This work presents a formalization in PVS of the computational theory for a computational
model given as a class of partial recursive functions called PVS0. The model is built over …

Este trabalho descreve a mecanização de propriedades computacionais de um modelo
funcional que tem sido aplicado para automatizar o raciocínio sobre a terminação de …