ON $\lambda$-DEFINABILITY OF ARITHMETICAL FUNCTIONS WITH INDETERMINATE VALUES OF ARGUMENTS

Authors

  • S.A. Nigiyan Chair of Programming and Information Technologies, YSU, Armenia

DOI:

https://doi.org/10.46991/PSYU:A/2016.50.2.039

Keywords:

arithmetical functions, indeterminate value of argument, monotonicity, computability, strong computability, $\lambda$-definability, algorithmic unsolvability

Abstract

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 \geq 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 \geq 2$, arithmetical function with indeterminate values of arguments, which has the diagonal property, is not $\lambda$-definable. It is proved that for any $k \geq 2$; 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.

Downloads

Published

2016-06-06

How to Cite

Nigiyan, S. (2016). ON $\lambda$-DEFINABILITY OF ARITHMETICAL FUNCTIONS WITH INDETERMINATE VALUES OF ARGUMENTS. Proceedings of the YSU A: Physical and Mathematical Sciences, 50(2 (240), 39–47. https://doi.org/10.46991/PSYU:A/2016.50.2.039

Issue

Section

Informatics