Computability theory of generalized functions

ABSTRACT

The theory of generalized functions is the foundation of the modern theory of partial differential equations (PDE). As computers are playing an ever-larger role in solving PDEs, it is important to know those operations involving generalized functions in analysis and PDE that can be computed on digital computers. In this article, we introduce natural concepts of computability on test functions and generalized functions, as well as computability on Schwartz test functions and tempered distributions. Type-2 Turing machines are used as the machine model [Weihrauch 2000]. It is shown here that differentiation and integration on distributions are computable operators, and various types of Fourier transforms and convolutions are also computable operators. As an application, it is shown that the solution operator of the distributional inhomogeneous three dimensional wave equation is computable.

REFERENCES

• 1: Barros-Neto, J. 1973. An introduction to the theory of distributions. In Pure and Applied Mathematics, vol. 14. Marcel Dekker Inc., New York.
• 2: Dunford, N., and Schwartz, J. T. 1959. Linear Operators Part I: General Theory. J. Wiley, New York.
• 3: Grzegorczyk, A. 1955. Computable functionals. Fund. Math. 42, 168--202.
• 4: Grzegorczyk, A. 1957. On the definitions of computable real continuous functions. Fund. Math. 44, 61--71.
• 5: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 6: Kreitz, C., and Weihrauch, K. 1985. Theory of representations. Theoret. Comput. Sci. 38, 35--53.
• 7: Myhill, J. 1971. A recursive function defined on a compact interval and having a continuous derivative that is not recursive. Mich. Math. J. 18, 97--98.
• 8: Dag Normann, Exact real number computations relative to hereditarily total functionals, Theoretical Computer Science, v.284 n.2, p.437-453, 28 July 2002 [doi>10.1016/S0304-3975(01)00100-1]
• 9: Odifreddi, P. 1989. Classical recursion theory. In Studies in Logic and the Foundations of Mathematics, vol. 125. North-Holland, Amsterdam, The Netherland.
• 10: Rauch, J. 1997. Partial differential equations, In Graduate Texts in Mathematics. 2nd ed. Springer, New York.
• 11: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 12: Schwartz, L. 1966. Théorie des Distributions. Hermann, Paris, France. Nouvelle édition.
• 13: Schröder, M. 2001. Admissible representations of limit spaces. In Computability and Complexity in Analysis, Jens Blanck, Vasco Brattka, and Peter Hertling, Eds. Lecture Notes in Computer Science. (Berlin, Springer, Germany), New York.
• 14: Turing, A. M. 1936. On computable numbers, with an application to the "Entscheidungsproblem." Proc. London Math. Soc. 42, 2, 230--265.
• 15: Washihara, M. 1999. Computability and tempered distributions. Math. Japon. 50, 1, 1--7.
• 16: Klaus Weihrauch, Computability, Springer-Verlag New York, Inc., New York, NY, 1987
• 17: Klaus Weihrauch, A Foundation for Computable Analysis, Proceedings of the 24th Seminar on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics, p.104-121, November 22-29, 1997
• 18: Klaus Weihrauch, Computability on the probability measures on the Borel sets of the unit interval, Theoretical Computer Science, v.219 n.1-2, p.421-437, May 28, 1999 [doi>10.1016/S0304-3975(98)00298-9]
• 19: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 20: Weihrauch, K., and Zhong, N. 2002. Is wave propagation computable or can wave computers beat the Turing machine? Proc. London Math. Soc. 85, 2, 312--332.
• 21: Zhong, N., and Weihrauch, K. 2000. Computability theory of generalized functions. Informatik Berichte 276, FernUniversität Hagen, Hagen. Sept.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.m Miscellaneous

General Terms:
Theory

Keywords:
Computable analysis, computability on distributions, computable real functions