Title: Models of computation for partial functions on the reals
Abstract: We compare models of computation for partial functions f:R⇀R. We consider four models: two concrete (Grzegorczyk–Lacombe and tracking computability), one abstract (approximability by a While program with “countable choice”) and a new hybrid model: multipolynomial approximability. We show that these four models are equivalent, under the two assumptions: the domain of f is the union of an effective exhaustion, i.e. a sequence of “stages”, each of which is a finite union of disjoint rational open intervals, and f is effectively locally uniformly continuous w.r.t. this exhaustion.
Publication Year: 2015
Publication Date: 2015-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 5
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot