WhileCC-approximability and Acceptability of Elementary Functions

Abstract

In this thesis, we study models of computation for partial functions on the reals. Existing work [Fu and Zucker, 2014, Tucker and Zucker, 1999, 2004] studies classes of computable partial functions on R, namely • GL-computability, • tracking computability, • multipolynomial approximability, and • WhileCC-approximability. 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 was previously unknown whether the class of acceptable functions is sufficiently large to include many common functions, such as the elementary functions. In this thesis, we solve the conjecture posed by Fu and Zucker [2014] and show that all elementary functions are acceptable. We also prove that the elementary functions are WhileCC -approximable and therefore computable in all the aforementioned models of computation.