I first note that there is an analogous construct
for numerically computing limits in Maple via the Levin's u-transform.
Theorem. Deterministic numerical evaluation of limits is impossible in general.
Remark This obviously implies that numerical calculation of sums is also impossible.
Proof. Suppose we are given an algorithm which purports to evaluate a limit, say to 2 decimal place accuracy, from some finite sample of the sequence (any computer program will have to be content with a finite sample for obvious reasons). Construct the following function:
spy := proc(n) global spylist; if type(n, posint) then spylist := spylist, n; 1 else 'spy'(args) fi end: spylist := NULL;
(The program is given in Maple syntax for convenience, but this is not restricted to Maple).
This program returns 1, no matter what its input is; thus it reflects the sequence which obviously has limit 1. But it also records the values of n it is called with, for our later perusal. If we run the purported limit algorithm with this function, the algorithm will (quickly, one hopes) return 1 as the limit. We then have a finite list of integers where the algorithm probed the sequence at; now we define a malicious sequence by
Since spylist is finite, this sequence is ultimately 0, and its limit is 0. But the algorithm for accelerating convergence cannot know that, because its probes cannot distinguish this sequence from . Q.E.D.
This proof is a modified version of Kahan's proof that numerical integration is impossible, if the integrator can't look into the subprogram defining the function. There are ways to defeat this proof (by adding randomness, for example) but one could similarly prove that no matter what the program was, there would exist sequences that would fool it.
I leave it as an exercise for the reader to spy on
to see what it actually does here.