[feanaro]

> But on the other hand why would you assume that you should find an intersection between two restrictive algorithms?

I think it's key here that these two algorithms are so basic and fundamental to the structure they are executed upon (the naturals) so that every other algorithm will use them in some way. The very notion of "algorithm over the naturals" and intuition of what it means for such an algorithm to be restrictive are determined by the nature of these operations.

Put like this, it seems far less obvious to me that there is an a priori reason why the results of these two operations should or shouldn't coincide. Both scenarios seem plausible before we study problems like these.