WhileCC-Approximability and Acceptability of Elementary Functions

WhileCC -Approximability and Acceptability of Elementary Functions Fateme Ghasemi and Jeffery Zucker Department of Computing and Software, McMaster University, Hamilton, ON, Canada [email protected] zuck[email protected] July 2025 In this work, we study models of computation for the reals. Previous work [Stoltenberg-Hansen and Tucker,1999,Tucker and Zucker,2005] focuses on computational models for total functions. However, the class of total functions is too restrictive: many standard functions in real analysis (such as the logarithmic, square root, and inverse trigonometric functions) are partial and cannot be studied under such models. Thus, in this work, we focus on the computability of partial functions. Existing work [Fu and Zucker,2014,Tucker and Zucker,1999,2004] investigates the classes of computable partial functions on Rarising from the models of GL-computability, tracking computability, multipolynomial approximability, and WhileCC -approximability. The first two classes correspond to concrete models of computation. In concrete models, computability depends on the representation of data. For example, an α-tracking computable function represents each real number as a natural number. In contrast, abstract models (such as WhileCC -programs) allow functions to be defined independently of such implementation details. For a programmer, this would be akin to writing programs against an abstract interface instead of dealing with specific implementations. Abstract models are easier to program in, but may not be as expressive as their concrete counterparts. Fu and Zucker [2014] show that all these four models of computation are equivalent when we restrict our attention to a specific class of functions we call “acceptable” functions. This means, within the realm of acceptable functions, we can work with WhileCC -approximability without giving up expressivity and transfer results amongst the models. However, it has been unknown whether the class of acceptable functions is sufficiently large to include many common functions, such as the elementary functions. In this work, we solve the conjecture posed by Fu and Zucker [2014] and show that all elementary functions are acceptable. We also prove that the 1 elementary functions are WhileCC -approximable and therefore computable in all the aforementioned models of computation. References M. Q. Fu and J. Zucker. Models of computation for partial functions on the reals. Journal of Logical and Algebraic Methods in Programming, 84(2):218–237, 11 2014. ISSN 2352-2208. doi:10.1016/j.jlamp.2014.11.001.1 V. Stoltenberg-Hansen and J. V. Tucker. Concrete models of computation for topological algebras. Theoretical Computer Science, 219(1-2):347–378, 1999. ISSN 0304-3975. doi:10.1016/S0304-3975(98)00296-5.1 J. Tucker and J. Zucker. Computable total functions on metric algebras, universal algebraic specifications and dynamical systems. The Journal of Logic and Algebraic Programming, 62(1):71–108, 2005. ISSN 1567-8326. doi:10.1016/j.jlap.2003.10.001.1 J. V. Tucker and J. I. Zucker. Computation by ‘While’ programs on topological partial algebras. Theoretical Computer Science, 219(1):379–420, 1999. ISSN 0304-3975. doi:10.1016/S0304-3975(98)00297-7.1 J. V. Tucker and J. I. Zucker. Abstract versus concrete computation on metric partial algebras. ACM Trans. Comput. Log., 5(4):611–668, 2004. doi:10.1145/1024922.1024924.1 2