This article is cited in 10 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.

MSC: Primary 68Q01; Secondary 68Q05

Received: 20.10.2014
Accepted: 17.12.2014

Language: English