|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2015, Issue 1, Pages 52–60
(Mi uzeru15)
|
|
|
|
This article is cited in 9 scientific papers (total in 9 papers)
Informatics
On non-classical theory of computability
S. A. Nigiyan Yerevan State University
Abstract:
Definition of arithmetical functions with indeterminate values of arguments is given. Notions of computability, strong computability and $\lambda$-definability for such functions are introduced. Monotonicity and computability of every $\lambda$-definable arithmetical function with indeterminate values of arguments is proved. It is proved that every computable, naturally extended arithmetical function with indeterminate values of arguments is $\lambda$-definable. It is also proved that there exist strong computable, monotonic arithmetical functions with indeterminate values of arguments, which are not $\lambda$-definable. The $\delta$-redex problem for strong computable, monotonic arithmetical functions with indeterminate values of arguments is defined. It is proved that there exist strong computable, $\lambda$-definable arithmetical functions with indeterminate values of arguments, for which the $\delta$-redex problem is unsolvable.
Keywords:
arithmetical function, indeterminate value of argument, computability, strong computability, $\lambda$-definability, $\beta$-redex, $\delta$-redex.
Received: 20.10.2014 Accepted: 17.12.2014
Citation:
S. A. Nigiyan, “On non-classical theory of computability”, Proceedings of the YSU, Physical and Mathematical Sciences, 2015, no. 1, 52–60
Linking options:
https://www.mathnet.ru/eng/uzeru15 https://www.mathnet.ru/eng/uzeru/y2015/i1/p52
|
Statistics & downloads: |
Abstract page: | 258 | Full-text PDF : | 71 | References: | 85 |
|