Site logo

ON NON-CLASSICAL THEORY OF COMPUTABILITY

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

CC BY-NC 4.0 This work is licensed under Creative Commons Attribution–NonCommercial International License (CC BY-NC 4.0).

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.

Subscribe to TheGufo Newsletter​