|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2015, Issue 2, Pages 45–52
(Mi uzeru24)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Informatics
On typed and untyped lambda-terms
T. V. Khondkaryan Yerevan State University
Abstract:
Typed λ-terms that use variables of any order and don’t use constants of order >1 are studied in the paper. Used constants of order 1 are strong computable functions and each of them has an untyped λ-term, which λ-defines it. Besides, for the set of built-in functions there exists such a notion of δ-reduction, that every typed term has a single normal form. An algorithm of translation of typed λ-terms to untyped λ-terms is presented. According to that algorithm, each typed term t is mapped to an untyped term t′. We study in which case typed terms t1,t2 such that t1→→βδt2 correspond to untyped terms t′1,t′2 such that t′1→→βt′2.
Keywords:
typed λ-terms, untyped λ-terms, translation, β-reduction,
δ-reduction.
Received: 28.04.2015 Accepted: 03.06.2015
Citation:
T. V. Khondkaryan, “On typed and untyped lambda-terms”, Proceedings of the YSU, Physical and Mathematical Sciences, 2015, no. 2, 45–52
Linking options:
https://www.mathnet.ru/eng/uzeru24 https://www.mathnet.ru/eng/uzeru/y2015/i2/p45
|
Statistics & downloads: |
Abstract page: | 107 | Full-text PDF : | 36 | References: | 63 |
|