McMaster University
WhileCC-approximability and Acceptability of Elementary Functions
Abstract
dc:description.abstractIn 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.
Degree
thesis:*- Department dc:contributor.department
- Computing and Software
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ghasemi, Fateme
- Advisor dc:contributor.advisor
-
- Zucker, Jeffery
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/25100