Abstract
We study computability on sequence spaces, as they are used in functional analysis. It is known that non-separable normed spaces cannot be admissibly represented on Turing machines. We prove that under the Axiom of Choice non-separable normed spaces cannot even be admissibly represented with respect to any compatible topology (a compatible topology is one which makes all bounded linear functionals continuous). Surprisingly, it turns out that when one replaces the Axiom of Choice by the Axiom of Dependent Choice and the Baire Property, then some non-separable normed spaces can be represented admissibly on Turing machines with respect to the weak topology (which is just the weakest compatible topology). Thus the ability to adequately handle sequence spaces on Turing machines sensitively relies on the underlying axiomatic setting.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brattka, V.: Computability on non-separable Banach spaces and Landau’s theorem. In: Crosilla, L., Schuster, P. (eds.) From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics, Oxford University Press, Oxford (to appear)
Ko, K.I.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston (1991)
Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin (1989)
Schäfer, H.H.: Topological Vector Spaces. Macmillan, New York (1966)
Schechter, E.: Handbook of Analysis and Its Foundations. Academic Press, San Diego (1997)
Schröder, M.: Extended admissibility. Theoretical Computer Science 284, 519–538 (2002)
Schröder, M.: Admissible Representations for Continuous Computations. PhD thesis, Fachbereich Informatik, FernUniversität Hagen (2002)
Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)
Werner, D.: Funktionalanalysis, 4th edn. Springer, Berlin (2002)
Willard, S.: General Topology. Addison-Wesley, Reading (1970)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brattka, V., Schröder, M. (2005). Computing with Sequences, Weak Topologies and the Axiom of Choice. In: Ong, L. (eds) Computer Science Logic. CSL 2005. Lecture Notes in Computer Science, vol 3634. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11538363_32
Download citation
DOI: https://doi.org/10.1007/11538363_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28231-0
Online ISBN: 978-3-540-31897-2
eBook Packages: Computer ScienceComputer Science (R0)