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

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 / Γ<!-- Γ --> ( x ) and Σ<!-- Σ --> n = 1 ∞<!-- ∞ --> ( 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 ) = Σ<!-- Σ --> i = 0 ∞<!-- ∞ --> 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.