It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological properties of continuous sets. I could not find any, except "Recursive Analysis" by R.L. Goodstein but I dont have any feedback on that book. I would also like to ask for suggestions regarding a book on Complexity over Real Numbers which again deals with the connection between the complexity and the topology of a set. The only book I found on the net was "Complexity and Real Computation" by Lenore Blum et al but I am not sure if that is the book which I am looking for. Thanks in advance.
2 Answers
There are some good books - 1. Computable Analysis - Pour-El and Richards (an older reference) 2. Computable Analysis - Weihrauch
There's also the Blum-Shub-Smale Model, which is the model explored in "Complexity and Real Computation".
The complexity theory of computability of reals is explored in 1. Computational Complexity of real functions - Ker-I Ko
A regular conference which explores this area is "Computability and Complexity in Analysis", held annually.
The website of Computability and Complexity in Analysis Network has extensive bibliography. See their page for books.
For computability, see
- Klaus Weihrauch, "Computable Analysis", 2010.
It also has a chpater on complexity.
See also PhD theses of Jens Blanc and Andrej Bauer.
Another interesting paper is
- Viggo Stoltenberg-Hansen and John Tucker, "Computability on Topological Spaces via Domain Representations", 1997.