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

HTML articles powered by AMS MathViewer

- by Marian Boykan Pour-el
- Trans. Amer. Math. Soc.
**199**(1974), 1-28 - DOI: https://doi.org/10.1090/S0002-9947-1974-0347575-8
- PDF | Request permission

## 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

- Tom M. Apostol,
*Mathematical analysis: a modern approach to advanced calculus*, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1957. MR**0087718**
V. Bush, - Alonzo Church,
*An Unsolvable Problem of Elementary Number Theory*, Amer. J. Math.**58**(1936), no. 2, 345–363. MR**1507159**, DOI 10.2307/2371045 - J. Crank,
*The Differential Analyser*, Longmans, Green and Co., London-New York-Toronto, 1947. MR**0025822** - A. Grzegorczyk,
*On the definitions of computable real continuous functions*, Fund. Math.**44**(1957), 61–71. MR**89809**, DOI 10.4064/fm-44-1-61-71
O. Hölder, - 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**, DOI 10.24033/asens.326
A. Jackson, - Clarence L. Johnson,
*Analog computer techniques*, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1956. MR**0122032** - Stephen Cole Kleene,
*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790**
G. A. Korn and T. M. Korn, - A. A. Markov,
*The theory of algorithms*, Amer. Math. Soc. Transl. (2)**15**(1960), 1–14. MR**0114753**, DOI 10.1090/trans2/015/01
G. Pólya, - 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**, DOI 10.1007/BF02404412 - H. G. Rice,
*Recursive real numbers*, Proc. Amer. Math. Soc.**5**(1954), 784–791. MR**63328**, DOI 10.1090/S0002-9939-1954-0063328-5 - Claude E. Shannon,
*Mathematical theory of the differential analyzer*, J. Math. Phys. Mass. Inst. Tech.**20**(1941), 337–354. MR**6251**, DOI 10.1002/sapm1941201337 - Walter W. Soroka,
*Analog methods in computation and simulation*, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1954. MR**0066052** - Ernst Specker,
*Nicht konstruktiv beweisbare Sätze der Analysis*, J. Symbolic Logic**14**(1949), 145–158 (German). MR**31447**, DOI 10.2307/2267043
W. Thomson (Lord Kelvin),

*The differential analyzer, a new machine for solving differential equations*, J. Franklin Inst.

**212**(1931), 447-488.

*Ueber die Eigenschaft der Gamma funktion keiner algebraischen Differentialgleichung zu genügen*, Math. Ann.

**28**(1887), 1-13.

*Analog computation*, McGraw-Hill, New York, 1960.

*Electronic analog and hybrid computers*, McGraw-Hill, New York, 1964. 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.

*Über das Anwachsen von ganzen Funktionen die einer Differentialgleichung genügen*, Viert. Naturforsch. Ges. Zürich

**61**(1916), 531-545.

*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. R. Tomovic and W. J. Karplus,

*High speed analog computers*, Wiley, New York, 1962. 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.

## Bibliographic Information

- © Copyright 1974 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**199**(1974), 1-28 - MSC: Primary 02F50; Secondary 68A55
- DOI: https://doi.org/10.1090/S0002-9947-1974-0347575-8
- MathSciNet review: 0347575