|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2016, Issue 2, Pages 39–47
(Mi uzeru157)
|
|
|
|
Informatics
On λ-definability of arithmetical functions with indeterminate values of arguments
S. A. Nigiyan Chair of Programming and Information Technologies YSU, Armenia
Abstract:
In this paper the arithmetical functions with indeterminate values of arguments are regarded. It is known that every λ-definable arithmetical function with indeterminate values of arguments is monotonic and computable. The λ-definability of every computable, monotonic, 1-ary arithmetical function with indeterminate values of arguments is proved. For computable, monotonic, k-ary, k⩾2, arithmetical functions with indeterminate values of arguments, the so-called diagonal property is defined. It is proved that every computable, monotonic, k-ary, k⩾2, arithmetical function with indeterminate values of arguments, which has the diagonal property, is not λ-definable. It is proved that for any k⩾2, the problem of λ-definability for computable, monotonic, k-ary arithmetical functions with indeterminate values of arguments is algorithmic unsolvable. It is also proved that the problem of diagonal property of such functions is algorithmic unsolvable, too.
Keywords:
arithmetical functions, indeterminate value of argument, monotonicity, computability, strong computability, λ-definability, algorithmic unsolvability.
Received: 22.01.2016 Accepted: 21.03.2016
Citation:
S. A. Nigiyan, “On λ-definability of arithmetical functions with indeterminate values of arguments”, Proceedings of the YSU, Physical and Mathematical Sciences, 2016, no. 2, 39–47
Linking options:
https://www.mathnet.ru/eng/uzeru157 https://www.mathnet.ru/eng/uzeru/y2016/i2/p39
|
Statistics & downloads: |
Abstract page: | 174 | Full-text PDF : | 60 | References: | 48 |
|