RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, Physical and Mathematical Sciences, 2017 Volume 51, Issue 1, Pages 46–52 (Mi uzeru330)

This article is cited in 5 papers

Informatics

On canonical notion of $\delta$-reduction and on translation of typed $\lambda$-terms into untyped $\lambda$-terms

S. A. Nigiyan, T. V. Khondkaryan

Chair of Programming and Information Technologies YSU, Armenia

Abstract: In the paper typed and untyped $\lambda$-terms are considered. Typed $\lambda$-terms use variables of any order and constants of order $\leq1$. Constants of order $1$ are strong computable functions with indeterminate values of arguments and every function has an untyped $\lambda$-term that $\lambda$-defines it. The so-called canonical notion of $\delta$-reduction is introduced. This is the notion of $\delta$-reduction that is used in the implementation of functional programming languages. For the canonical notion of $\delta$-reduction the translation of typed $\lambda$-terms into untyped $\lambda$-terms is studied.

Keywords: typed $\lambda$-term, untyped $\lambda$-term, translation, notion of $\delta$-reduction, $\lambda$-definability.

MSC: 68N18

Received: 18.10.2016
Accepted: 25.11.2016

Language: English



© Steklov Math. Inst. of RAS, 2024