Models of computation for partial functions on the reals

• We compare 4 models of computation for partial functions on the reals.
• These satisfy “domain exhaustion” and continuity assumptions.
• We conjecture they include all elementary functions on the reals.

We compare models of computation for partial functions f:R⇀Rf: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:(1)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(2)f is effectively locally uniformly continuous w.r.t. this exhaustion. These assumptions seem to hold for all unary elementary functions of real analysis, many of which are, of course, partial. We make a conjecture with regard to this.