ON NON-CLASSICAL THEORY OF COMPUTABILITY

Authors

  • S.A. Nigiyan Chair of Programming and Information Technologies, YSU, Armenia

DOI:

https://doi.org/10.46991/PSYU:A/2015.49.1.052

Keywords:

arithmetical function, indeterminate value of argument, computability, strong computability, λ-definability, β-redex, δ-redex

Abstract

Definition of arithmetical functions with indeterminate values of arguments is given. Notions of computability, strong computability and λ-definability for such functions are introduced. Monotonicity and computability of every λ-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 λ-definable. It is also proved that there exist strong computable, monotonic arithmetical functions with indeterminate values of arguments, which are not λ-definable. The δ-redex problem for strong computable, monotonic arithmetical functions with indeterminate values of arguments is defined. It is proved that there exist strong computable, λ-definable arithmetical functions with indeterminate values of arguments, for which the δ-redex problem is unsolvable.

Downloads

Published

2015-03-16

How to Cite

Nigiyan, S. (2015). ON NON-CLASSICAL THEORY OF COMPUTABILITY. Proceedings of the YSU A: Physical and Mathematical Sciences, 49(1 (236), 52–60. https://doi.org/10.46991/PSYU:A/2015.49.1.052

Issue

Section

Informatics