On the functions generated by the general purpose analog computer

DOI10.1016/J.IC.2017.09.015MaRDI QIDQ1680506zbMATH OpenOpenAlexFDO

Authors Olivier Bournez, Amaury Pouly, Daniel Graça

Publication date 16 November 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.00546, http://hdl.handle.net/10400.1/10083

zbMATH Keywords

analog computationcontinuous-time computationsgeneral-purpose analog computerreal computations

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78)

Abstract: We consider the General Purpose Analog Computer (GPAC), introduced by Claude Shannon in 1941 as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. We extend the model properly to a model of computation not restricted to univariate functions (i.e. functions $f:mathbbRomathbbR$) but also to the multivariate case of (i.e. functions $f:mathbb{R}^{n}omathbb{R}^m$), and establish some basic properties. In particular, we prove that a very wide class of (continuous and discontinuous) functions can be uniformly approximated over their full domain. Technically: we generalize some known results about the GPAC to the multidimensional case: we extend naturally the notion of emph{generable} function, from the unidimensional to the multidimensional case. We prove a few stability properties of this class, mostly stability by arithmetic operations, composition and ODE solving. We establish that generable functions are always analytic. We prove that generable functions include some basic (useful) generable functions, and that we can (uniformly) approximate a wide range of functions this way. This extends some of the results from cite{Sha41} to the multidimensional case, and this also strengths the approximation result from cite{Sha41} over a compact domain to a uniform approximation result over unbounded domains. We also discuss the issue of constants, and we prove that involved constants can basically assumed to always be polynomial time computable numbers.

Recommendations

• Analog computers and recursive functions over the reals.
• Approximability in the GPAC
• Theory and Applications of Models of Computation
• Some recent developments on Shannon's General Purpose Analog Computer
• Analog networks on function data streams

Cites work

• scientific article; zbMATH DE number 1817650 (Why is no real title available?)
• scientific article; zbMATH DE number 42077 (Why is no real title available?)
• scientific article; zbMATH DE number 49374 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1564073 (Why is no real title available?)
• scientific article; zbMATH DE number 5224002 (Why is no real title available?)
• A short proof of the generalized Faà di Bruno's formula
• Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers)
• Analog computers and recursive functions over the reals.
• Computing with polynomial ordinary differential equations
• Higher chain formula proved by combinatorics
• Mathematical Theory of the Differential Analyzer
• On the complexity of solving initial value problems
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Some recent developments on Shannon's General Purpose Analog Computer
• The differential analyzer. A new machine for solving differential equations

Cited in

(15)

• Some recent developments on Shannon's General Purpose Analog Computer
• Characterizing time computational complexity classes with polynomial differential equations
• Analog networks on function data streams
• A Survey on Analog Models of Computation
• A universal ordinary differential equation
• Iteration, inequalities, and differentiability in analog computers
• scientific article; zbMATH DE number 5855087 (Why is no real title available?)
• Some mathematical limitations of the general-purpose analog computer
• Computing with polynomial ordinary differential equations
• scientific article; zbMATH DE number 4141382 (Why is no real title available?)
• scientific article; zbMATH DE number 4106109 (Why is no real title available?)
• Approximability in the GPAC
• Tracking computability of GPAC-generable functions
• Theory and Applications of Models of Computation
• A continuous characterization of PSPACE using polynomial ordinary differential equations

This page was built for publication: On the functions generated by the general purpose analog computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1680506)