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)



Abstract computability and its relation to the general purpose analog computer (some connections between logic, differential equations and analog computers)

Author: Marian Boykan Pour-el
Journal: Trans. Amer. Math. Soc. 199 (1974), 1-28
MSC: Primary 02F50; Secondary 68A55
MathSciNet review: 0347575
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Our aim is to study computability from the viewpoint of the analog computer. We present a mathematical definition of an analog generable function of a real variable. This definition is formulated in terms of a simultaneous set of nonlinear differential equations possessing a ``domain of generation.'' (The latter concept is explained in the text.) Our definition includes functions generated by existing general-purpose analog computers. Using it we prove two theorems which provide a characterization of analog generable functions in terms of solutions of algebraic differential polynomials. The characterization has two consequences. First we show that there are entire functions which are computable (in the sense of recursive analysis) but which cannot be generated by any analog computer in any interval--e.g. $ 1/\Gamma (x)$ and $ \Sigma _{n = 1}^\infty ({x^n}/{n^{({n^3})}})$. Second we note that the class of analog generable functions is very large: it includes special functions which arise as solutions to algebraic differential polynomials. Although not all computable functions are analog generable, a kind of converse holds. For entire functions, $ f(x) = \Sigma _{i = 0}^\infty {b_i}{x^i}$, the theorem takes the following form. If $ f(x)$ is analog generable on some closed, bounded interval then there is a finite number of $ {b_k}$ such that, on every closed bounded interval, $ f(x)$ is computable relative to these $ {b_k}$. A somewhat similar theorem holds if $ f$ is not entire. Although the results are stated and proved for functions of a real variable, they hold with minor modifications for functions of a complex variable.

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

  • [1] Tom M. Apostol, Mathematical analysis: a modern approach to advanced calculus, Addison-Wesley Publishing Company, Inc., Reading, Mass., 1957. MR 0087718
  • [2] V. Bush, The differential analyzer, a new machine for solving differential equations, J. Franklin Inst. 212 (1931), 447-488.
  • [3] Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345–363. MR 1507159, 10.2307/2371045
  • [4] J. Crank, The Differential Analyser, Longmans, Green & Co., London, New York, Toronto, 1947. MR 0025822
  • [5] A. Grzegorczyk, On the definitions of computable real continuous functions, Fund. Math. 44 (1957), 61–71. MR 0089809
  • [6] O. Hölder, Ueber die Eigenschaft der Gamma funktion keiner algebraischen Differentialgleichung zu genügen, Math. Ann. 28 (1887), 1-13.
  • [7] A. Hurwitz, Sur le développement des fonctions satisfaisant à une équation différentielle algébrique, Ann. Sci. École Norm. Sup. (3) 6 (1889), 327–332 (French). MR 1508828
  • [8] A. Jackson, Analog computation, McGraw-Hill, New York, 1960.
  • [9] Clarence L. Johnson, Analog computer techniques, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1956. MR 0122032
  • [10] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
  • [11] G. A. Korn and T. M. Korn, Electronic analog and hybrid computers, McGraw-Hill, New York, 1964.
  • [12] D. Lacombe, Extension de la notion de fonctions récursive aux fonctions d'une ou plusieurs variables réelles. I,II,III, C.R. Acad. Sci. Paris 240 (1955), 2478-2480; ibid. 241 (1955), 13-14, 151-153. MR 17, 225.
  • [13] A. A. Markov, The theory of algorithms, Amer. Math. Soc. Transl. (2) 15 (1960), 1–14. MR 0114753
  • [14] G. Pólya, Über das Anwachsen von ganzen Funktionen die einer Differentialgleichung genügen, Viert. Naturforsch. Ges. Zürich 61 (1916), 531-545.
  • [15] Georg Pólya, Zur Untersuchung der Grössenordnung ganzer Funktionen, die einer Differentialgleichung genügen, Acta Math. 42 (1920), no. 1, 309–316 (German). MR 1555169, 10.1007/BF02404412
  • [16] H. G. Rice, Recursive real numbers, Proc. Amer. Math. Soc. 5 (1954), 784–791. MR 0063328, 10.1090/S0002-9939-1954-0063328-5
  • [17] Claude E. Shannon, Mathematical theory of the differential analyzer, J. Math. Phys. Mass. Inst. Tech. 20 (1941), 337–354. MR 0006251
  • [18] Walter W. Soroka, Analog methods in computation and simulation, McGraw-Hill Book Company, Inc., New York-Toronto-London, 1954. MR 0066052
  • [19] Ernst Specker, Nicht konstruktiv beweisbare Sätze der Analysis, J. Symbolic Logic 14 (1949), 145–158 (German). MR 0031447
  • [20] W. Thomson (Lord Kelvin), On an instrument for calculating the integral of the product of two given functions, Proc. Roy. Soc. London 24 (1876), 266-268. See also pp. 269-271 and pp. 271-275.
  • [21] R. Tomovic and W. J. Karplus, High speed analog computers, Wiley, New York, 1962.
  • [22] A. Turing, On computable numbers with an application to the Entscheindungsproblem, Proc. London Math. Soc. (2) 42 (1937), 230-265; ibid. (2) 43 (1938), 544-546.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F50, 68A55

Retrieve articles in all journals with MSC: 02F50, 68A55

Additional Information

Keywords: General purpose analog computer, recursive function, recursive analysis, computable function of a real variable, algebraic differential polynomial, Cauchy-Peano existence theorem for differential equations, Picard-Lindelöf theorem, transcendental field extensions, Gamma function
Article copyright: © Copyright 1974 American Mathematical Society