This article is cited in 1 paper

Informatics

On $\lambda$-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 $\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.

MSC: 68Q01; 68Q05

Received: 22.01.2016
Accepted: 21.03.2016

Language: English