Premium
The basis decision problem in λ‐calculus
Author(s) -
Intrigila Benedetto
Publication year - 1993
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19930390120
Subject(s) - mathematics , basis (linear algebra) , calculus (dental) , set (abstract data type) , element (criminal law) , decision problem , algebra over a field , pure mathematics , algorithm , computer science , geometry , medicine , dentistry , political science , law , programming language
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.