On λ-definability of arithmetical functions with indeterminate values of arguments (Արգումենտների անորոշ արժեքներով թվաբանական ֆունկցիաների λ-որոշելիության մասին)

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.