[FOM] Primitive recursive reals
joeshipman at aol.com
Thu Apr 20 19:04:20 EDT 2006
Harvey Friedman <friedman at math.ohio-state.edu> wrote:
> QUESTION: Is e + pi primitive recursive in base 2, base 10, or even
> 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
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
More information about the FOM