Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Computability and noncomputability in classical analysis


Authors: Marian Boykan Pour-El and Ian Richards
Journal: Trans. Amer. Math. Soc. 275 (1983), 539-560
MSC: Primary 03D80; Secondary 03F60, 26E05, 42A20, 47A99
DOI: https://doi.org/10.1090/S0002-9947-1983-0682717-1
MathSciNet review: 682717
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper treats in a systematic way the following question: which basic constructions in real and complex analysis lead from the computable to the noncomputable, and which do not? The topics treated include: computability for $ {C^n}$, $ {C^\infty }$, real analytic functions, Fourier series, and Fourier transforms. A final section presents a more general approach via "translation invariant operators". Particular attention is paid to those processes which occur in physical applications. The approach to computability is via the standard notion of recursive function from mathematical logic.


References [Enhancements On Off] (What's this?)

  • [1] O. Aberth, Computable analysis, McGraw-Hill, New York, 1980.
  • [2] Errett Bishop, Foundations of constructive analysis, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0221878
  • [3] L. E. J. Brouwer, De Onbetrouwbaarheid der Logische Principes (the untrustworthiness of the principles of logic), Tijdschrift voor Wijsbegeerte, Amsterdam, vol. 2, 1908, 152-158.
  • [4] A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 0086756
  • [5] A. Grzegorczyk, On the definitions of computable real continuous functions, Fund. Math. 44 (1957), 61–71. MR 0089809
  • [6] A. Heyting, Intuitionism: An introduction, Second revised edition, North-Holland Publishing Co., Amsterdam, 1966. MR 0221911
  • [7] Yitzhak Katznelson, An introduction to harmonic analysis, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0248482
  • [8] G. Kreisel, A notion of mechanistic theory, Synthese 29 (1974), 11-16.
  • [9] D. Lacombe, Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles. I, II, III, C. R. Acad. Sci. Paris 240 (1955), 2478-2480; 241 (1955), 13-14; 241 (1955), 151-153.
  • [10] Yiannis N. Moschovakis, Notation systems and recursive ordered fields, Compositio Math. 17 (1965), 40–71 (1965). MR 0181569
  • [11] J. Myhill, A recursive function, defined on a compact interval and having a continuous derivative that is not recursive, Michigan Math. J. 18 (1971), 97–98. MR 0280373
  • [12] Marian Boykan Pour-El and Jerome Caldwell, On a simple definition of computable function of a real variable—with applications to functions of a complex variable, Z. Math. Logik Grundlagen Math. 21 (1975), 1–19. MR 0366638
  • [13] M. B. Pour-El and I. Richards, Differentiability properties of computable functions—a summary, Acta Cybernet. 4 (1978/79), no. 1, 123–125. MR 521457
  • [14] Marian Boykan Pour-El and Ian Richards, A computable ordinary differential equation which possesses no computable solution, Ann. Math. Logic 17 (1979), no. 1-2, 61–90. MR 552416, https://doi.org/10.1016/0003-4843(79)90021-4
  • [15] Marian Boykan Pour-El and Ian Richards, The wave equation with computable initial data such that its unique solution is not computable, Adv. in Math. 39 (1981), no. 3, 215–239. MR 614161, https://doi.org/10.1016/0001-8708(81)90001-3
  • [16] N. A. Šanin, Constructive real numbers and constructive function spaces, Translated from the Russian by E. Mendelson. Translations of Mathematical Monographs, Vol. 21, American Mathematical Society, Providence, R.I., 1968. MR 0229508
  • [17] J. C. Shepherdson, On the definition of computable function of a real variable, Z. Math. Logik Grundlagen Math. 22 (1976), no. 5, 391–402. MR 0441704
  • [18] Ernst Specker, Der Satz vom Maximum in der rekursiven Analysis, Constructivity in mathematics: Proceedings of the colloquium held at Amsterdam, 1957 (edited by A. Heyting), Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1959, pp. 254–265 (German). MR 0107603
  • [19] E. C. Titchmarsh, The theory of functions, Oxford Univ. Press, New York, 1939.
  • [20] I. D. Zaslavskii, Some properties of constructive real numbers and constructive functions, Amer. Math. Soc. Transl. (2) 57 (1966), 1-84.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D80, 03F60, 26E05, 42A20, 47A99

Retrieve articles in all journals with MSC: 03D80, 03F60, 26E05, 42A20, 47A99


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1983-0682717-1
Article copyright: © Copyright 1983 American Mathematical Society