[FOM] Primitive recursive reals

[Timothy Y. Chow]

Joe Shipman wrote:
> 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).

I mentioned this to Joe Shipman directly, but then figured maybe it's 
worth posting to FOM.

It's long been appreciated that base-b representations are the wrong 
representation for computational questions.  There is a fairly good 
understanding now of how to represent real numbers in a robust manner that 
allows issues of, say, computational complexity to be addressed (although 
the subject is still immature compared to classical recursion theory, and 
many important foundational questions remain unanswered).  A good 
introduction to the subject is an article that I think has already been 
mentioned on FOM, namely Braverman and Cook's article in the March 2006 
Notices of the AMS: "Computing over the Reals: Foundations of Scientific 
Computing."

This does not address Joe Shipman's specific question about *canonical* 
representations, though.

Tim