Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
Questions regarding real-number computation and infinite iteration, especially in analysis and topology, are studied in constructive and computable analysis. Most people who work in this area will tell you that while the BSS model can be useful for certain kinds of computational complexity, it does not properly reflect computability on real numbers. The trouble is with the decidable $&lt;$ relation on the reals, which is a basic building block in the BSS model.

There are several computational models which capture both computation of (exact) real numbers and infinite computation. Your examples all reduce to computation of the limit of a convergent sequence whose rate of convergence is explicitly known. This is a well-studied situation.

Here is one possible way of understanding computation on real numbers. I will use Haskell just for fun (usually these things get explained in terms of Turing machines). Let us think of a real number as a convergent sequence of rational approximations,


  type R = Int -&gt; Rational


where we require that the $k$-th approximation is at most $2^{-k}$ away from the limit (we could have chosen some other rate of convergence, too, or we could have equipped each approximation sequence with information about the rate of convergence--the important thing is that the rate of convergence has to be provided explicitly).

Addition can be defined as follows:


  add x y = \k -&gt; x (k+1) + y (k+1)


Exercise: define multiplication and other arithmetic operations.

Now to get infinite iteration going, we need an operation lim which takes a Cauchy sequence and computes its limit. More precisely, lim takes two arguments: a Cauchy sequence $(a_n)_n$ and its modulus of convergence $m$, which is a map $m : \mathbb{N} \to \mathbb{N}$ such that $a_{m(k)}$ is at most $2^{-k}$ away from the limit of $(a_n)_n$. In Haskell:


  lim :: (Int -&gt; R) -&gt; (Int -&gt; Int) -&gt; R
  
  lim a m = \k -&gt; a (m (k+1)) (k+1)


Exercise: compute $\sqrt{r}$ as the limit of the sequence obtained by Newton's method for finding the positive root of $x^2 - r$.

This is just a very brief outline on how to do things. To find out more, visit the CCA net web site, especially the Texts and Monographs page.