Logic Journal of IGPL · 2003 · 35 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsProgramming LanguagesTheory Of ComputationEquivalence CheckingMatching TheoryModel TheoryPredicate LogicType CheckingType SystemsDecidabilityDecidability ProblemsLambda CalculusMatching AlgorithmsMatching ProblemsTyped Lambda Calculus
Abstract We show that the solvability of matching problems in the simply typed λ-calculus, up to β equivalence, is not decidable. This decidability question was raised by Huet [4]. Note that there are two variants of the question: that concerning β equivalence (dealt with here), and that concerning βη equivalence. The second of these is perhaps more interesting; unfortunately the work below sheds no light on it, except perhaps to illustrate the subtlety and difficulty of the problem.
8
A unification algorithm for typed λ-calculus
G. Huet · Theoretical Computer Science · 1975 · 509 citations
The undecidability of unification in third order logic
Gérard Huet · Information and Control · 1973 · 103 citations
Completeness, invariance and <i>λ</i>-definability
Rick Statman · Journal of Symbolic Logic · 1982 · 95 citations