Geodesic
On $\lambda$-definability of arithmetical functions with indeterminate values of arguments
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2016), pp. 39-47 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper the arithmetical functions with indeterminate values of arguments are regarded. It is known that every $\lambda$-definable arithmetical function with indeterminate values of arguments is monotonic and computable. The $\lambda$-definability of every computable, monotonic, $1$-ary arithmetical function with indeterminate values of arguments is proved. For computable, monotonic, $k$-ary, $k\ge2$, arithmetical functions with indeterminate values of arguments, the so-called diagonal property is defined. It is proved that every computable, monotonic, $k$-ary, $k\ge2$, arithmetical function with indeterminate values of arguments, which has the diagonal property, is not $\lambda$-definable. It is proved that for any $k\ge2,$ the problem of $\lambda$-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, $\lambda$-definability, algorithmic unsolvability. 
@article{UZERU_2016_2_a6,
     author = {S. A. Nigiyan},
     title = {On $\lambda$-definability of arithmetical functions with indeterminate values of arguments},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {39--47},
     year = {2016},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2016_2_a6/}
}
TY  - JOUR
AU  - S. A. Nigiyan
TI  - On $\lambda$-definability of arithmetical functions with indeterminate values of arguments
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2016
SP  - 39
EP  - 47
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZERU_2016_2_a6/
LA  - en
ID  - UZERU_2016_2_a6
ER  - 
%0 Journal Article
%A S. A. Nigiyan
%T On $\lambda$-definability of arithmetical functions with indeterminate values of arguments
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2016
%P 39-47
%N 2
%U http://geodesic.mathdoc.fr/item/UZERU_2016_2_a6/
%G en
%F UZERU_2016_2_a6
S. A. Nigiyan. On $\lambda$-definability of arithmetical functions with indeterminate values of arguments. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2016), pp. 39-47. http://geodesic.mathdoc.fr/item/UZERU_2016_2_a6/

[1] Z. Manna, Mathematical Theory of Computation, McGraw-Hill Book Company, 1974 | MR | Zbl

[2] S.A. Nigiyan, “On Non-classical Theory of Computability”, Proceedings of the YSU. Physical $\$ Mathematical Sciences, 2015, no. 1, 52–60 | Zbl

[3] H. Barendregt, The Lambda Calculus. Its Syntax and Semantics, North-Holland Publishing Company, 1981 | MR | Zbl

[4] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Company, 1967 | MR | Zbl