[FOM] Primitive recursive reals

[joeshipman@aol.com]

Harvey Friedman <friedman at math.ohio-state.edu> wrote:
> QUESTION: Is e + pi primitive recursive in base 2, base 10, or even 
(as
> expected) primitive recursive in every base?

The whole discussion seems to suggest that maybe we should seek to 
reformulate constructive analysis in terms of a representation of real 
numbers that has nicer properties than "base b" notation; a 
representation in which the standard arithmetic operations preserve 
primitive recursivity (and, it is to be hoped, preserve much sharper 
computational properties such as polynomial-time computability).

Let's say that, instead of a sequence of rational approximations 
(r1,r2,r3,...) to a real number r, we require that real numbers be 
represented by a sequence of rational approximations such that the nth 
term r_n is guaranteed to be within 1/f(n) of r, where f is some 
primitive recursive integer function. Then the arithmetic operations 
are nicely computable, and easily approximable numbers like pi have 
obviously primitive recursive representations. Any number in complexity 
class X in "base b" notation for some b would also b in complexity 
class X under the new scheme.

Now, the obvious objection to this is that "base b" notation has the 
nice property of almost-uniqueness (it is the "almost" that causes the 
problems that have been discussed, such as the basic arithmetic 
operations not preserving primitive recursiveness).

To meet this objection, we need some way to pass from a "primitive 
recursive real number" (in the sense that both the approximating 
rational sequence (r1,r2,r3,...) and the modulus of approximation f(n) 
are primitive recursive functions) to a canonical primitive recursive 
representation of the same number.

Is this possible?

Let me state the question more formally. Suppose that f, g, and h are 
primitive recursive functions whose domain and range is the positive 
integers, such that the intersection of the sequence of open rational 
intervals

((f(i)/g(i))-(1/h(i)),(f(i)/g(i))+(1/h(i)))

is (the singleton set containing) a non-negative real number r.

For any real number so representable, there are many different 
"presentations" (f,g,h). Can we find a canonical one, that is, a 
mapping defined on triples of primitive recursive functions such that 
when (f1,g1,h1) and (f2,g2,h2) both represent the same real number then 
they are mapped to the same triple? Let's stipulate that we don't care 
where (f,g,h) is mapped if it does not actually represent a real number 
(that is, the sequence of intervals does not have an intersection 
consisting of a single point).

The mapping would have to be computable in terms of the indices of the 
primitive recursive functions, but would not itself have to be 
primitive recursive.

-- JS




-- JS