A computable version of Banach’s Inverse Mapping Theorem

Annals of Pure and Applied Logic 157 (2-3):85-96 (2009)
  Copy   BIBTEX

Abstract

Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based theory of computability on Euclidean space and other topological spaces. Using a computable version of Banach’s Inverse Mapping Theorem we can answer the first question positively. Hence, the non-uniform version of the inversion problem is solvable, while a topological argument shows that the uniform version is not. Thus, we are in the striking situation that any computable linear operator has a computable inverse while there exists no general algorithmic procedure to transfer a program of the operator into a program of its inverse. As a consequence, the computable version of Banach’s Inverse Mapping Theorem is a powerful tool which can be used to produce highly non-constructive existence proofs of algorithms. We apply this method to prove that a certain initial value problem admits a computable solution. As a preparation of Banach’s Inverse Mapping Theorem we also study the Open Mapping Theorem and we show that the uniform versions of both theorems are limit computable, which means that they are effectively -measurable with respect to the effective Borel hierarchy

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,410

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Computability of solutions of operator equations.Volker Bosserhoff - 2007 - Mathematical Logic Quarterly 53 (4):326-344.
Borel complexity and computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
Computable Riesz representation for the dual of C [0; 1].Hong Lu & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4):415-430.
A uniformly computable Implicit Function Theorem.Timothy H. McNicholl - 2008 - Mathematical Logic Quarterly 54 (3):272-279.
Comparing Computability in Two Topologies.Djamel Eddine Amir & Mathieu Hoyrup - 2024 - Journal of Symbolic Logic 89 (3):1232-1250.
Turing computable embeddings.Julia Knight, Sara Miller & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
Turing computable embeddings.F. Knight Julia, Miller Sara & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.

Analytics

Added to PP
2013-12-22

Downloads
30 (#624,304)

6 months
9 (#347,620)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Add more citations

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Effective Borel measurability and reducibility of functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Borel complexity and computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
Quelques procédés de définition en topologie récursive.Daniel Lacombe - 1959 - Journal of Symbolic Logic 31 (1):129--158.

Add more references