×

Consistency argument and classification problem in \(\lambda\)-calculus. (English) Zbl 1003.03515

Summary: Enlightened by Mal’tsev’s theorem in universal algebra, a new criterion for consistency arguments in \(\lambda\)-calculus is introduced. It is equivalent to that of Jacopini and Baeten-Boerboom, but more convenient to use. Based on the new criterion, we use an enhanced technique to show a few results which provide a deeper insight in the classification problem for \(\lambda\)-terms with no normal forms.

MSC:

03B40 Combinatory logic and lambda calculus
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jacopini, G., {\(\lambda\)}-calculus and computer science theory,Lecture Notes in Computer Science, 1975, 37: 213. · doi:10.1007/BFb0029527
[2] Baeten, J., Boerboom, B., {\(\Omega\)} can be anything it should not be,Indagationes Math., 1979, 41: 111. · Zbl 0417.03006
[3] Burris, S., Sankappanavar, H. P.,A Course in Universal Algebra, Berlin: Springer-Verlag, 1981.
[4] Barendregt, H. P.,The Lambda Calculus: Its Syntax and Semantics, Amsterdam: North-Holland, 1984. · Zbl 0551.03007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.