Silly question: Computing with computable numbers...

Question

Of course the point to this question, to the extent there is such a thing, is the answer below. Was about to post that as a "question"; instead, to make this a legal Q&A thing:

Question. Can one concoct a "computable" data type allowing "exact" computations with computable numbers?

Ok, to clarify what I'm asking: To avoid various problems with decimal representations, let's say that $x\in\Bbb R$ is computable if there exists an algorithm $Approx$ such that for any $\epsilon>0$, $Approx(\epsilon)$ returns a rational $r$ with $|x-r|<\epsilon$. Regarding the word "exact" above and below: If we know the $Approx$ function then it gives us an "exact representation" of $x$, in the strongest sense possible for a generic computable number: We can get as many decimals as we want, if we're willing to wait.

So as object including an $Approx$ method is in a sense an exact representation of the computable number $x$. (Of course I'm assuming a system with arbitrarily large integers (often called "infinite precision", which I mention just to say I'm not the only one using language in funny ways as in my usage of "exact"), hence exact arithmetic with arbitrarry rationals.) The question is how we can define things like $x+y$ and $xy$. Addition is very simple; as in the code below, $|(x+y)-(x.Approx(\epsilon/2)+y.Approx(\epsilon/2))|<\epsilon$, so we just say that $(x+y).Approx(\epsilon)$ should return $x.Approx(\epsilon/2)+y.Approx(\epsilon/2)$.

Multiplication is slightly trickier. We need to calculate $\delta_j$ such that $|xy-x.Approx(\delta_1)y.Approx(\delta_2)|<\epsilon$. The proof that multiplication is continuous gives us such $\delta_j$, but in terms of $x$ and $y$. It's enough to have a rational upper bound for $|x|$, and we can get that just by setting $x.UpperBound()$ to $|x.Approx(1)|+1$.

For a while I was stuck on $x/y$, since there's no way to use $y.Approx()$ to determine whether $y=0$. But on second thhought I decided that's an unreasonable requirement: If I'm using floating point I don't expect the system to test whether $y=0$ before letting me ask for $x/y$, and I certainly don't attempt to test the floating-point representation of $y$ for equality with $0$; instead it's my responsibility not to request $x/y$ unless I already know for some mathematical reason that in fact $y\ne0$.

And if we say it's the programmer's responsibility to know that $y\ne0$ before asking for $x/y$ then division is no problem. Again, the proof that divison is continuous gives us $\delta_j$. The problem is that (if in fact $y\ne0$) we need a rational $r$ with $|y|\ge r>0$ to calculate $\delta_2$. And it's easy to give an "algorithm" that returns such an $r$ if one exists, if we're willing to settle for an infinite loop if there is no such $r$, taking the attitude that in that case the problem is the programmer's fault for requesting $x/y$ without knowing that $y\ne0$:

def LowerBound(self):
  eps = 1
  b=0
  while not(b-eps > 0):
    eps = eps/2
    b=abs(self.Approx(eps))
  return b - eps

Maybe just to be friendly we keep track of the number of iterations and throw a possible-division-by-zero error at some point...

Answer 1

Was thinking about stability of Gaussian elimination. Of course one way to fix things is to do exact computations with rationals. Then I say to myself wait, one can also do "exact" computations with computable numbers.

Alas that doesn't help with Gaussian elimination, since there's no way to tell whether a computable number equals zero. But I wonder whether anyone's ever added a "computable" data type to some language.

For example, a computable class in Python that supports addition (untested, probably typos):

class computable:
  def __init__(self, approx):
    self.approx = approx
  def __add__(self, other):
    return sum(self, other)

class sum(computable):
  def __init__(self, x, y):
    self.x = x
    self.y = y
  def approx(self, eps):
    return self.x.approx(eps/2)+self.y.approx(eps/2)

def PiApprox(eps):
  "returns an approximation of pi using some algorithm"

pi = computable(PiApprox)

and now not only is pi an "exact representation of" $\pi$, in addition pi+pi is exactly $\pi+\pi$. No, I'm not claiming that this is good for anything more than a chuckle, but it does seem possibly amusing.