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

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?)

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

American Mathematical Society