The basis decision problem in λ‐calculus
Benedetto Intrigila · Mathematical logic quarterly · 1993
Abstract We show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable. MSC: 03B40, 03D35.