SICP Exercise 2.16

Question

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Answer

It is not an exaggeration to say that this problem is very difficult. As a matter of fact, it is so difficult that, as far as I know, nobody has solved it yet.

That being said, it is still an interesting question so let’s look at why this is so difficult.

As mentioned in my answer to exercise 2.15, the core problem here is the question of identity. Identity is not a problem in regular arithmetic, because if, for example, $x=4$, then every single instance of $x$ will be exactly equal to every other instance of $x$, that is, $4$. But if $x$ was an interval, then one $x$ and another $x$ could, in theory, represent different values.

For example, let us assume that $x$ is the interval $[5,15]$. Now $\frac{x}{x}$ could be $1$, if it stood for $\frac{5}{5}$ or $\frac{11}{11}$ or something like that. But what if it is $\frac{6}{14}$? These are both legitimate values for $x$ and are within the specified range. The problem is, we don’t know what the values are.

So in order to fix this, we would have to find some way to introduce identity into the system, for which there is no simple way in pure mathematics. This is known as the Dependency Problem. If you are interested, here is a link to the Wikipedia article.