<p>(Disclaimer: I am not an expert, feel free to suggest corrections, or write a more comprehensive answer if you are.)</p>

<p>Extending computability and complexity to the real numbers (which is a first step in doing analysis) is tricky and has been done in several inequivalent ways. One is the Blum-Shub-Smale (BSS) model, which augments Turing machines with the ability to store and perform algebraic operations with real numbers. The resulting theory is algebraic in flavor, e.g. all computable functions are piecewise semi-algebraic. The model is interesting but has some strange features that make it seem unrealistic, at least as a model of how computers actually deal with real number computation. For example it allows computation with uncomputable constants: the constant function with value <a href="http://en.wikipedia.org/wiki/Chaitin%27s_constant" rel="noreferrer">Chaitin's constant</a> is computable in the BSS model. On the other hand, $e^x$ is not computable in the BSS model.</p>

<p>Another approach can be found in the field of <em>computable analysis</em>, and I think that's what you are looking for. Check the <a href="http://www.fernuni-hagen.de/weihrauch/index_data/book.html" rel="noreferrer">book by Weihrauch</a> for an introduction (the introduction and the chapter on computable real numbers are available on the linked page, and will give you a good idea of what is going on). There still are several not quite equivalent models here, but the rough idea is that rational numbers have finite representation, and then you construct the computable reals the same way you construct the reals as a completion of the rationals. So, analogously to defining a real as a (equivalence class of) a Cauchy sequence of rationals, a computable real is given by a Turing machine that computes arbitrarily good approximations to it. Then a function $f: \mathbb{R} \to \mathbb{R}$ is computable if a Turing machine can compute arbitrarily good approximations of $f(x)$ given (as an oracle) a machine that computes arbitrarily good approximations of $x$. </p>

<p>There are fascinating connections between computable analysis and classical/modern analysis and many other fields, for example algorithmic randomness. One simple example of a theorem is that all computable functions are continuous. To give a more sophisticated example (without actually going into the details), there are interesting counterparts to classical theorems in analysis, e.g. an analogue of Rademacher's theorem is that all computable Lipschitz functions $f:[0,1] \to [0,1]$ are differentiable at all algorithmically random points (for the right notion of algorithmic randomness). </p>

<p>Formulating a complexity theory for real functions is, AFAIK, even trickier. This is related to the fact that computing a real function is a higher-order computation (since it takes a Turing machine as input) so the bit size of the input is not usually the right thing to measure the runtime against. Check this <a href="http://arxiv.org/abs/cs/0502066" rel="noreferrer">paper by Mark Braverman</a> for one approach to defining efficient real computation. At this point I am way out of my depth to say more, so I will stop.</p>

CC BY-SA 3.0
2015-05-30T17:31:11.817Z
2015-06-03T04:06:00.697Z
2015-06-03T04:06:00.697Z
Sasho Nikolov
<p>The classic reference for complexity of computation of real functions is:</p>

<ul>
<li>Ker-I Ko, Computational Complexity of Real Functions, 1991</li>
</ul>

<p>Also have a look at chapter 7 in Weirauch's book.</p>

CC BY-SA 3.0
2015-05-31T07:39:34.853Z
2015-05-31T07:39:34.853Z
Kaveh
<p>Looking at this question more than two years after it was posted and, no offense, I'm disappointed with the answers and comments.</p>

<p>This is what happens when CS departments all over the world mislabel their topics and mislead multiple generations of scientists and engineers.</p>

<ul>
<li><p>Either the <em>Algorithms</em> classes in all CS departments need to be relabelled to <em>Discrete Algorithms</em>.</p></li>
<li><p>Or the current content of that class needs to be cut down to 50% or less (that 50% or less includes <em>Data Structures</em>) and the remaining half needs to include some assortment of topics from <em>Numerical Analysis</em> and <em>Scientific Computing</em>.</p></li>
</ul>

<p>Because what is the core of <em>Mathematical Analysis</em>? <em>Real Analysis</em> and the real line. And how are real numbers represented in computers? floating point, or arbitrary precision, etc. So the next time you're working on any algorithm that deals with floating point and/or arbitrary precision as a core component (not as a content, as in sorting a bunch of floating point numbers), know that you're doing <em>Algorithmic Mathematical Analysis</em> (AMA)!</p>

<p>And don't even get me started with the massive universe of NA/Computational Science topics. It arguably dwarfs whole of TCS. When you're solving systems of multiple non-linear PDEs on a computer, you're not only utilizing the fundamentals of mathematical analysis, but cutting edge functional analysis in all its glory, complete with open research problems, etc. It can't get any more AMA than that.</p>

CC BY-SA 3.0
2017-09-30T03:06:48.213Z
I don't understand how your rant about the CS curriculum answers the question.
Sasho Nikolov
CC BY-SA 3.0
2017-09-30T03:13:44.393Z
Well I don't understand how the rest of the answers and comments to this date answer even 1% of the question. And yet they're there. (some are even upvoted, and one is even accepted). And maybe 40% of my comment is not directly relevant to the question (though it indirectly is), yet the remaining 60% pretty much settles the issue.
Fi Zixer
CC BY-SA 3.0
2017-09-30T03:19:11.043Z
The accepted answer gives a website with a wealth of information about computability and complexity over the reals. That's what the question asked for. It did not ask for opinions on the appropriateness of the CS curriculum.
Sasho Nikolov
CC BY-SA 3.0
2017-10-02T14:52:36.240Z
We generally tend to downvote rants. If you had simply said that *numerical analysis* was, in some sense, algorithmic mathematical analysis, you might actually have gotten some upvotes. And, really, multiple generations of scientists and engineers have ***not*** been misled. You seem to be assuming that they're stupid. They're not; they know the difference between the stuff taught in algorithms classes and the stuff taught in numerical analysis classes.
Peter Shor 
CC BY-SA 3.0
2017-09-30T02:48:27.990Z
2017-09-30T03:07:11.347Z
2017-09-30T03:07:11.347Z
Fi Zixer
<p>Check out
the <a href="http://cca-net.de" rel="noreferrer">Computability and Complexity in Analysis</a> network. Quote:</p>
<blockquote>
<p>The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of exact real arithmetic, as well as further developments of already existing software packages.</p>
</blockquote>

CC BY-SA 3.0
2015-05-30T09:40:58.013Z
2015-05-30T09:40:58.013Z
2020-06-17T09:38:08.363Z
Bjørn Kjos-Hanssen
<p>There are <em>algorithmic</em> graph theory/number theory/combinatorics/information theory/game theory.</p>

<blockquote>
  <p>Is there algorithmic mathematical analysis?</p>
</blockquote>

<p>According to wiki, <a href="https://en.wikipedia.org/wiki/Mathematical_analysis">mathematical analysis</a> includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on <a href="https://en.wikipedia.org/wiki/Real_analysis">real analysis (wiki)</a> that deals with the real numbers and real-valued functions of a real variable.</p>

<p>"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.</p>

<hr>

<p>Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.</p>

CC BY-SA 3.0
2015-05-30T04:38:19.243Z
I think you are looking for "computable analysis", which is by now a quite well-established area. You can check, for example, an introductory book by Weihrauch. The theory deals mainly with computability questions, I am not sure how much is known as far as computational complexity. My impression is that even nailing a good definition of complexity is tricky.
Sasho Nikolov
CC BY-SA 3.0
2015-05-30T04:52:27.270Z
@SashoNikolov Yes. "Computable analysis" seems very relevant. Thanks. Convert your comment to an answer?
hengxin
CC BY-SA 3.0
2015-05-30T06:43:44.240Z
See also Chaudhuri, Sankaranarayanan and Vardi's paper on Regular Real analysis which studies a fragment of real analysis you can carry out with finite automata on infinite words.
Vijay D
CC BY-SA 3.0
2015-06-03T04:42:24.823Z
As another resource, see Yap's paper "Theory of Real Computation according to EGC": http://www.cs.nyu.edu/exact/doc/realtheory.pdf
Huck Bennett
<cc.complexity-theory><reference-request><soft-question><computability>
Is there algorithmic mathematical analysis?
hengxin
# Is there algorithmic mathematical analysis?

(Asked by: username_0 on 2015-05-30)

There are *algorithmic* graph theory/number theory/combinatorics/information theory/game theory.

> Is there algorithmic mathematical analysis?

According to wiki, [mathematical analysis](https://en.wikipedia.org/wiki/Mathematical_analysis) includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on [real analysis (wiki)](https://en.wikipedia.org/wiki/Real_analysis) that deals with the real numbers and real-valued functions of a real variable.

"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.

---

Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.

**Tags:** cc.complexity-theory, reference-request, soft-question, computability
> **Comments:**
> **username_1**: I think you are looking for "computable analysis", which is by now a quite well-established area. You can check, for example, an introductory book by Weihrauch. The theory deals mainly with computability questions, I am not sure how much is known as far as computational complexity. My impression is that even nailing a good definition of complexity is tricky.  
> **username_0**: @SashoNikolov Yes. "Computable analysis" seems very relevant. Thanks. Convert your comment to an answer?  
> **username_2**: See also Chaudhuri, Sankaranarayanan and Vardi's paper on Regular Real analysis which studies a fragment of real analysis you can carry out with finite automata on infinite words.  
> **username_3**: As another resource, see Yap's paper "Theory of Real Computation according to EGC": http://www.cs.nyu.edu/exact/doc/realtheory.pdf  

---

## 4 answers

### Answer by username_7 on 2015-05-30. Score: 18 | Accepted answer

Check out
the [Computability and Complexity in Analysis](http://cca-net.de) network. Quote:

> The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of exact real arithmetic, as well as further developments of already existing software packages.


---

### Answer by username_1 on 2015-05-30. Score: 12

(Disclaimer: I am not an expert, feel free to suggest corrections, or write a more comprehensive answer if you are.)

Extending computability and complexity to the real numbers (which is a first step in doing analysis) is tricky and has been done in several inequivalent ways. One is the Blum-Shub-Smale (BSS) model, which augments Turing machines with the ability to store and perform algebraic operations with real numbers. The resulting theory is algebraic in flavor, e.g. all computable functions are piecewise semi-algebraic. The model is interesting but has some strange features that make it seem unrealistic, at least as a model of how computers actually deal with real number computation. For example it allows computation with uncomputable constants: the constant function with value [Chaitin's constant](http://en.wikipedia.org/wiki/Chaitin%27s_constant) is computable in the BSS model. On the other hand, $e^x$ is not computable in the BSS model.

Another approach can be found in the field of *computable analysis*, and I think that's what you are looking for. Check the [book by Weihrauch](http://www.fernuni-hagen.de/weihrauch/index_data/book.html) for an introduction (the introduction and the chapter on computable real numbers are available on the linked page, and will give you a good idea of what is going on). There still are several not quite equivalent models here, but the rough idea is that rational numbers have finite representation, and then you construct the computable reals the same way you construct the reals as a completion of the rationals. So, analogously to defining a real as a (equivalence class of) a Cauchy sequence of rationals, a computable real is given by a Turing machine that computes arbitrarily good approximations to it. Then a function $f: \mathbb{R} \to \mathbb{R}$ is computable if a Turing machine can compute arbitrarily good approximations of $f(x)$ given (as an oracle) a machine that computes arbitrarily good approximations of $x$.

There are fascinating connections between computable analysis and classical/modern analysis and many other fields, for example algorithmic randomness. One simple example of a theorem is that all computable functions are continuous. To give a more sophisticated example (without actually going into the details), there are interesting counterparts to classical theorems in analysis, e.g. an analogue of Rademacher's theorem is that all computable Lipschitz functions $f:[0,1] \to [0,1]$ are differentiable at all algorithmically random points (for the right notion of algorithmic randomness).

Formulating a complexity theory for real functions is, AFAIK, even trickier. This is related to the fact that computing a real function is a higher-order computation (since it takes a Turing machine as input) so the bit size of the input is not usually the right thing to measure the runtime against. Check this [paper by Mark Braverman](http://arxiv.org/abs/cs/0502066) for one approach to defining efficient real computation. At this point I am way out of my depth to say more, so I will stop.


---

### Answer by username_4 on 2015-05-31. Score: 8

The classic reference for complexity of computation of real functions is:

* Ker-I Ko, Computational Complexity of Real Functions, 1991

Also have a look at chapter 7 in Weirauch's book.


---

### Answer by username_5 on 2017-09-30. Score: -7

Looking at this question more than two years after it was posted and, no offense, I'm disappointed with the answers and comments.

This is what happens when CS departments all over the world mislabel their topics and mislead multiple generations of scientists and engineers.

* Either the *Algorithms* classes in all CS departments need to be relabelled to *Discrete Algorithms*.
* Or the current content of that class needs to be cut down to 50% or less (that 50% or less includes *Data Structures*) and the remaining half needs to include some assortment of topics from *Numerical Analysis* and *Scientific Computing*.

Because what is the core of *Mathematical Analysis*? *Real Analysis* and the real line. And how are real numbers represented in computers? floating point, or arbitrary precision, etc. So the next time you're working on any algorithm that deals with floating point and/or arbitrary precision as a core component (not as a content, as in sorting a bunch of floating point numbers), know that you're doing *Algorithmic Mathematical Analysis* (AMA)!

And don't even get me started with the massive universe of NA/Computational Science topics. It arguably dwarfs whole of TCS. When you're solving systems of multiple non-linear PDEs on a computer, you're not only utilizing the fundamentals of mathematical analysis, but cutting edge functional analysis in all its glory, complete with open research problems, etc. It can't get any more AMA than that.

> **Comments:**
> **username_1**: I don't understand how your rant about the CS curriculum answers the question.  
> **username_5**: Well I don't understand how the rest of the answers and comments to this date answer even 1% of the question. And yet they're there. (some are even upvoted, and one is even accepted). And maybe 40% of my comment is not directly relevant to the question (though it indirectly is), yet the remaining 60% pretty much settles the issue.  
> **username_1**: The accepted answer gives a website with a wealth of information about computability and complexity over the reals. That's what the question asked for. It did not ask for opinions on the appropriateness of the CS curriculum.  
> **username_6**: We generally tend to downvote rants. If you had simply said that *numerical analysis* was, in some sense, algorithmic mathematical analysis, you might actually have gotten some upvotes. And, really, multiple generations of scientists and engineers have ***not*** been misled. You seem to be assuming that they're stupid. They're not; they know the difference between the stuff taught in algorithms classes and the stuff taught in numerical analysis classes.  

---

