<p>There are two examples of a complexity-theoretic study of iterative methods. The class <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pls" rel="nofollow">PLS</a> and the recent work by <a href="http://www.siam.org/proceedings/soda/2011/SODA11_061_daskalakisc.pdf" rel="nofollow">Papadimitriou and Daskalakis</a> on CLS: continuous local search. These might be useful (especially the latter as it deals with continuous domains)</p>

CC BY-SA 2.5
2011-03-22T18:12:27.380Z
2011-03-23T20:00:56.420Z
2011-03-23T20:00:56.420Z
Suresh Venkat
<p>Questions regarding real-number computation and infinite iteration, especially in analysis and topology, are studied in <em>constructive and computable analysis</em>. 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.</p>

<p>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.</p>

<p>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,</p>

<blockquote>
  <p><code>type R = Int -&gt; Rational</code></p>
</blockquote>

<p>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).</p>

<p>Addition can be defined as follows:</p>

<blockquote>
  <p><code>add x y = \k -&gt; x (k+1) + y (k+1)</code></p>
</blockquote>

<p>Exercise: define multiplication and other arithmetic operations.</p>

<p>Now to get infinite iteration going, we need an operation <code>lim</code> which takes a Cauchy sequence and computes its limit. More precisely, <code>lim</code> takes <em>two</em> arguments: a Cauchy sequence $(a_n)_n$ and its <em>modulus of convergence</em> $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:</p>

<blockquote>
  <p><code>lim :: (Int -&gt; R) -&gt; (Int -&gt; Int) -&gt; R</code></p>
  
  <p><code>lim a m = \k -&gt; a (m (k+1)) (k+1)</code></p>
</blockquote>

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

<p>This is just a very brief outline on how to do things. To find out more, visit the <a href="http://cca-net.de/" rel="nofollow">CCA net</a> web site, especially the <a href="http://cca-net.de/publications/books.html" rel="nofollow">Texts and Monographs</a> page.</p>

CC BY-SA 2.5
2011-03-22T18:36:18.957Z
2011-03-22T18:36:18.957Z
Andrej Bauer
<p>I know the <a href="http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow">Blum-Shub-Smale model</a>. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.</p>

<p>A very general question:
Most algorithms compromise of
finite input - finite computation steps - finite output</p>

<p>However, in mathematics most schemes which one could call algorithmic actually compromise infinitely many iterations. Just to name a few:</p>

<ul>
<li>Iteration to construct fix-points of contractive maps</li>
<li>Iterative solvers in numerical analysis</li>
<li>Newtons method</li>
</ul>

<p>I know the last one is treated in the classical book "Complexity and Real Computation" by Blum, Cucker, Shub &amp; Smale, but there does not seem to exist a generalization which puts "iterative" algorithms onto solid foundations.</p>

<p>Edit:
Yes, the question: </p>

<blockquote>
  <p>How can you deal with these iterative algorithms (which as such are not necessarily supposed to finish)?</p>
</blockquote>

<p>Addendum:
I always wondered whether there might be something like a BSS-like model, which is tailored for numerical analysis - in that it does formalize errors, inexactness, approximate solutions, and does not allow for "unreasonable" computing power. And is easy to access.</p>

<p>The book mentioned above is concerned about this gap, too:
"There is not even a formal definition of algorithm in the subject [of numerical analysis]" (p. 23). However, it does not seem their approach suits this need. On the other hand, the monograph Andrej mentions does include a book which heads towards this direction. </p>

CC BY-SA 2.5
2011-03-22T18:13:50.903Z
What is your question?
Jeffε
CC BY-SA 2.5
2011-03-22T22:49:41.313Z
possibly related: [The reasons for BSS (real-RAM) model being prefered in Computational Geometry](http://cstheory.stackexchange.com/q/2119/)
Kaveh
<cc.complexity-theory><algebraic-complexity><computing-over-reals><na.numerical-analysis><computable-analysis>
Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
shuhalo
# Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)

(Asked by: username_0 on 2011-03-22)

I know the [Blum-Shub-Smale model](http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine). It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.

A very general question:
Most algorithms compromise of
finite input - finite computation steps - finite output

However, in mathematics most schemes which one could call algorithmic actually compromise infinitely many iterations. Just to name a few:

* Iteration to construct fix-points of contractive maps
* Iterative solvers in numerical analysis
* Newtons method

I know the last one is treated in the classical book "Complexity and Real Computation" by Blum, Cucker, Shub & Smale, but there does not seem to exist a generalization which puts "iterative" algorithms onto solid foundations.

Edit:
Yes, the question:

> How can you deal with these iterative algorithms (which as such are not necessarily supposed to finish)?

Addendum:
I always wondered whether there might be something like a BSS-like model, which is tailored for numerical analysis - in that it does formalize errors, inexactness, approximate solutions, and does not allow for "unreasonable" computing power. And is easy to access.

The book mentioned above is concerned about this gap, too:
"There is not even a formal definition of algorithm in the subject [of numerical analysis]" (p. 23). However, it does not seem their approach suits this need. On the other hand, the monograph Andrej mentions does include a book which heads towards this direction.

**Tags:** cc.complexity-theory, algebraic-complexity, computing-over-reals, na.numerical-analysis, computable-analysis
> **Comments:**
> **username_1**: What is your question?  
> **username_2**: possibly related: [The reasons for BSS (real-RAM) model being prefered in Computational Geometry](http://cstheory.stackexchange.com/q/2119/)  

---

## 2 answers

### Answer by username_4 on 2011-03-22. Score: 9 | Accepted answer

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 $<$ 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 -> 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 -> 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 -> R) -> (Int -> Int) -> R`
>
> `lim a m = \k -> 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](http://cca-net.de/) web site, especially the [Texts and Monographs](http://cca-net.de/publications/books.html) page.


---

### Answer by username_3 on 2011-03-22. Score: 3

There are two examples of a complexity-theoretic study of iterative methods. The class [PLS](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aP#pls) and the recent work by [Papadimitriou and Daskalakis](http://www.siam.org/proceedings/soda/2011/SODA11_061_daskalakisc.pdf) on CLS: continuous local search. These might be useful (especially the latter as it deals with continuous domains)


---

