|
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 $\lambda$-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 $\lambda$-term, which $\lambda$-defines it. Besides, for the set of built-in functions there exists such a notion of $\delta$-reduction, that every typed term has a single normal form. An algorithm of translation of typed $\lambda$-terms to untyped $\lambda$-terms is presented. According to that algorithm, each typed term $t$ is mapped to an untyped term $t^{\prime}$. We study in which case typed terms $t_1, t_2$ such that $t_1\to\to_{\beta\delta}t_2$ correspond to untyped terms $t_1^{\prime},\, t_2^{\prime}$ such that $t_1^{\prime}\to\to_{\beta} t_2^{\prime}$.
Keywords:
typed $\lambda$-terms, untyped $\lambda$-terms, translation, $\beta$-reduction,
$\delta$-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: | 91 | Full-text PDF : | 28 | References: | 57 |
|