Geodesic
On non-classical theory of computability
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2015), pp. 52-60 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{UZERU_2015_1_a10,
     author = {S. A. Nigiyan},
     title = {On non-classical theory of computability},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {52--60},
     year = {2015},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2015_1_a10/}
}
TY  - JOUR
AU  - S. A. Nigiyan
TI  - On non-classical theory of computability
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2015
SP  - 52
EP  - 60
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UZERU_2015_1_a10/
LA  - en
ID  - UZERU_2015_1_a10
ER  - 
%0 Journal Article
%A S. A. Nigiyan
%T On non-classical theory of computability
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2015
%P 52-60
%N 1
%U http://geodesic.mathdoc.fr/item/UZERU_2015_1_a10/
%G en
%F UZERU_2015_1_a10
S. A. Nigiyan. On non-classical theory of computability. Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2015), pp. 52-60. http://geodesic.mathdoc.fr/item/UZERU_2015_1_a10/

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

[2] S.A. Nigiyan, “Arithmetical Functions with Indeterminate Values of Arguments. Computability and $\lambda$-Definability”, Reports of NAS RA, 114:1 (2014), 7–13 (in Russian) | MR

[3] A.I. Malcev, Algorithms and Recursive Functions, Nauka, M., 1986 (in Russian) | MR

[4] H. Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT: McGraw-Hill Book Company, Cambridge, Massachusetts, 1967 | MR

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