On non-classical theory of computability
Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 1 (2015), pp. 52-60
Voir la notice de l'article provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
number = {1},
year = {2015},
language = {en},
url = {http://geodesic.mathdoc.fr/item/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/