Can you suggest some (real-life) applications of Computable Analysis?
http://en.wikipedia.org/wiki/Computable_analysis
Why don't we just use classical analysis?
Henk, I have given this a few days thought, I think you are mistaken.
Computable Analysis is the treatment of Analysis with methods from recursion theory. It is not about discarding "non-constructive" analysis, it is about seeing it in new light. It is not un-usable. In fact, it can be seen as an upgrade of analysis.
Analysis is about approximation, so computable analysis is about effective approximation.
You obtain your result using classical analysis, and by using computable analysis you ask if there is a program that will obtain this result.
This is done by "effectivization" in the following way:
0. Fix some object, call it X, that you want to approximate with simpler objects. (you basically do this in classical analysis already)
1. Assign objects you want to use for approximation to each element of |N = {0,1,2,3,...}, and name this collection C (this assignment is surjective). Your objects can be real numbers, rationals, sequences, open balls with rational center and radius etc.
2. Fix an integer N, and set your working precision epsilon = 2^-N (this is an effective version of the well known epsilon > 0).
3. Is there a recursive function F: |N -> |N that will give for each input N the object F(N) = c_N from C that approximates X within error of epsilon = 2^-N ?
If there is such a recursive function then we say that X is computable.
Almost all definitions in computable analysis are the effective (computable) versions of the classic definitions. We use them to introduce algorithms into analysis (when ever possible) making choice in analysis somewhat more constructive (the "choice function" being the recursive function F from step 3).
Examples:
Definition 1:
A sequence of rationals {r_k} is a computable sequence of rationals if there exist computable functions a,b,s: |N -> |N such that r_k = (-1)^s(k) a(k) / b(k)
Definition 2:
A sequence of rationals {r_k} effectively converges to a real number x if there exists a recursive function e : |N -> |N such that for all N
k >= e(N) implies |r_k - x|
Dear Henk,
As much as I would like to agree with you that computability in analysis has no application whatsoever, I feel the need to think about it further, thank you for that.
Here is a question to ponder: What is the use of recursion theory in mathematics ?
I think the answer to this question will illuminate the need to do "computable mathematics". We CAN do without computability of course, to answer my second question.
But for me the answer is this: It is not about the computable (this is the easy part) but about the UNCOMPUTABLE.
For me, when something is uncomputable, the road does not end there, it is a statement about what we should do next in mathematics.
It means that every time you encounter a problem of this uncomputable type, you must invent a new algorithm for it (or if you wish, a new theory).
Simply put, there is NO one algorithm to solve them ALL.
And this is an opportunity for mathematicians to invent new methods, add new assumptions, invent new theories, new types of objects, etc. for solving each instance of this problem.
Let me give you an example:
The Halting Problem is undecidable right ? Yes, it is.
But can we restrict the type of programs that we consider ? Again, the answer is YES.
There is certainly is a subset of the Halting Problem that is decidable (for example a set of all programs without any loops), in fact there are many such subsets.
Each of them gives a new ground for mathematical investigation how to solve this "restricted" Halting problem.
So, to answer my first question, computable analysis is actually recursion theory in disguise, telling us what parts of analysis are computable and what are not. With computable things we already know how to deal, and the "uncomputables" are actually an invitation to deal with them (usually each being a new problem by itself) and make future progress in mathematics.
Kind Regards,
Konrad Burnik
- Badges
- Science topic
- Similar topics
- Mathematics