Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)


Standard and normal reductions

Author: R. Hindley
Journal: Trans. Amer. Math. Soc. 241 (1978), 253-271
MSC: Primary 03B40
MathSciNet review: 492300
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Curry and Feys' original standardization proof for $ \lambda \beta $-reduction is analyzed and generalized to $ \lambda \beta \eta $-reductions with extra operators.

There seem to be two slightly different definitions of 'standard reduction' in current use, without any awareness that they are different; it is proved that although these definitions turn out to be equivalent for $ \lambda \beta $-reduction, they become different for $ \lambda \beta \eta $ and for reductions involving extra operators, for example the recursion operator.

Normal reductions are also studied, and it is shown that the basic normal-reduction theorem stays true when fairly simple operators like Church's $ \delta $ and Curry's iterator Z are added, but fails for more complicated ones like the recursion operator R.

Finally, a table is given summarizing the results, and showing how far the main theorems on $ \lambda \beta $-reductions extend to reductions with various extra operators.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03B40

Retrieve articles in all journals with MSC: 03B40

Additional Information

PII: S 0002-9947(1978)0492300-7
Keywords: Reduction, lambda-conversion, combinator, standard reduction, normal reduction, Gross reduction, delta-conversion, recursion combinator
Article copyright: © Copyright 1978 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia