Algebraic Characterizations of Computable Analysis Real Functions
Walid Gomaa
Computable analysis is an approach to real continuous computation that is based on extending the normal Turing machine model. It was introduced by A. Turing 1936, A. Grzegorczyk 1955, and D. Lacombe 1955. Since the introduction of Moore’s real recursion theory in 1996 several classes of computable analysis functions have been characterized by functions algebras. On the one hand these algebraic characterizations provide a unifying theoretical framework that interconnects computable analysis with other approaches to real computation such as the GPAC and Moore’s recursion theory. On the other hand they provide machine-independent characterizations and hence a different perspective on computable analysis, a perspective that is more intuitive and natural especially from the vantage point of the mathematical analysis community. In this article we give an introduction to the field of computable analysis and a survey of the different algebraic characterizations of computable analysis classes starting from the elementary functions up to the total computable ones passing through the Grzegorczyk hierarchy. Unfortunately, not much work has been done in characterizing the sub elementary, in particular the lower complexity-theoretic classes. Some of the author’s published work in that latter direction are presented in this article. This includes the introduction of a function algebra that is an extension of the Bellantoni-Cook class. The extended class can exactly characterize discrete polynomial time computation, however, can only partially characterize polynomial time real computation. Furthermore, there exists a gap between the computation concept over the rational numbers and the corresponding one over the reals. This difference is illustrated by the existence of computable rational functions whose extension to the reals are not computable and vice versa. Understanding this gap might help us extend the algebraic discrete complexity classes to the reals. This article surveys many of the major results in the area and their implications.
Keywords: Computable Analysis, Function Algebra, Real computation, Polynomial Time, Oracle Turing Machine