Abstract Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. A pioneering model is the General Purpose Analog Computer (GPAC), initially presented by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams; however, it has been shown to be strictly less powerful than other models of computation on the reals, such as computable analysis. In previous work, we proposed an extension of the Shannon GPAC, denoted LGPAC, designed to overcome its limitations. Not only is the LGPAC model capable of expressing computation over general data spaces $\mathcal{X}$, but it also directly incorporates approximating computations by means of a limit module. An important feature of this work is the generalisation of the framework of the computation theory from Banach to Fréchet spaces. In this paper, we compare the LGPAC with a digital model of computation based on effective representations (tracking computability). We establish general conditions under which LGPAC-generable functions are tracking computable.

Most of the physical processes arising in nature are modeled by either ordinary or partial differential equations. From the point of view of analog computability, the existence of an effective way to obtain solutions of these systems is essential. A pioneering model of analog computation is the General Purpose Analog Computer (GPAC), introduced by Shannon as a model of the Differential Analyzer and improved by Pour-El, Lipshitz and Rubel, Costa and Gra\c{c}a and others. Its power is known to be characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations. We address one of the limitations of this model, concerning the notion of approximability, a desirable property in computation over continuous spaces that is however absent in the GPAC. In particular, the Shannon GPAC cannot be used to generate non-differentially algebraic functions which can be approximately computed in other models of computation. We extend the class of data types using networks with channels which carry information on a general complete metric space $X$; for example $X=C(R,R)$, the class of continuous functions of one real (spatial) variable. We consider the original modules in Shannon's construction (constants, adders, multipliers, integrators) and we add \emph{(continuous or discrete) limit} modules which have one input and one output. We then define an L-GPAC to be a network built with $X$-stream channels and the above-mentioned modules. This leads us to a framework in which the specifications of such analog systems are given by fixed points of certain operators on continuous data streams. We study these analog systems and their associated operators, and show how some classically non-generable functions, such as the gamma function and the zeta function, can be captured with the L-GPAC.

In (Tucker, J. V. and Zucker, J. I. (2007) Computability of analog networks. Theoret. Comput. Sci., 371, 115–146; Tucker, J. V. and Zucker, J. I. (2011) Continuity of operators on continuous and discrete time streams. Theoret. Comput. Sci., 412, 3378–3403), Tucker and Zucker present a model for the semantics of analog networks operating on streams from topological algebras. Central to their model is a parametrized stream operator representing the network along with a theory that concerns the existence, uniqueness, continuity and computability of a fixed point of that stream operator. We narrow the scope of this paper from general topological algebras to algebras of streams that assume values only from a Banach space. This restriction facilitates the definition of a fairly broad class of stream operators to which the theory described in the above two papers applies. As a demonstration in their original work, the authors provide two case studies: analog networks that model the behavior of simple mass-spring-damper systems. The case studies showcase the theory well, but they seem to require the imposition of somewhat peculiar conditions on the parameters (the masses, the spring constants and the damping coefficients). The extra conditions—while not catastrophic to the case studies—make them somewhat unsatisfying. We show here that while their original mass–spring–damper models do not fall within our new class, they can be trivially reconfigured into equivalent models that do. This modification obviates the extra conditions on the parameters.

In the theory of computation on topological algebras there is a considerable gap between so-called abstract and concrete models of computation. In concrete models, unlike abstract models, the computations depend on the representation of the algebra. First, we show that with abstract models, one needs algebras with partial operations, and computable functions that are both continuous and many-valued. This many-valuedness is needed even to compute single-valued functions, and so abstract models must be nondeterministic even to compute deterministic problems. As an abstract model, we choose the "while"-array programming language, extended with a nondeterministic "countable choice" assignment, called the WhileCC* model. Using this, we introduce the concept of approximable many-valued computation on metric algebras. For our concrete model, we choose metric algebras with effective representations. We prove:(1) for any metric algebra A with an effective representation α, WhileCC* approximability implies computability in α, and (2) also the converse, under certain reasonable conditions on A. From (1) and (2) we derive an equivalence theorem between abstract and concrete computation on metric partial algebras. We give examples of algebras where this equivalence holds.

Abstract computable functions are defined by abstract finite deterministic algorithms on many-sorted algebras. We show that there exist finite universal algebraic specifications that specify uniquely (up to isomorphism) (i) all abstract computable functions on any many-sorted algebra; (ii) all functions effectively approximable by abstract computable functions on any metric algebra. We show that there exist universal algebraic specifications for all the classically computable functions on the set ℝ of real numbers. The algebraic specifications used are mainly bounded universal equations and conditional equations. We investigate the initial algebra semantics of these specifications, and derive situations where algebraic specifications precisely define the computable functions.

Abstract We develop a theory of function tables, similar to, and inspired by, that given in the work of D. Parnas. We consider, in particular, two classes of function tables: normal and inverted. We study effective transformations between tables of these two classes, as well as transformations which change the dimension of a table. We also consider the interrelationship between these three types of transformation.

Intensional logic is applied to the semantics of an Algol-like programming language. This approach associates with expressions their senses, or meanings relative to possible worlds, here interpreted as machine states. These meanings lie in the semantic domains of a higher order typed intensional logic. The advantage of the approach is that it preserves compositionality of the meaning function, even in opaque contexts. This study extends earlier work in this direction, by T.M.V. Janssen and P. Van Emde Boas (1977), to pointers, including dereferenced pointers on both sides of assignments. It is shown how this approach gives an elegant solution to the problem of pointer semantics which is simple, compositional, and implementation independent.>

Transition systems as proposed by Hennessy & Plotkin are defined for a series of three languages featuring concurrency.The first has shuffle and local nondeterminancy, the second synchronization merge and local nondeterminacy, and the third synchronization merge and global nondeterminacy.The languages are all uniform in the sense that the elementary actions are uninterpreted.Throughout, infinite behaviour is taken into account and modelled with infinitary languages in the sense of Nivat.A comparison with denotational semantics is provided.For the first two languages, a linear time model suffices; for the third language a braching time model with processes in the sense of De Bakker & Zucker is described.In the comparison an important role is played by an intermediate semantics in the style of Hoare & Olderog's specification oriented semantics.A variant on the notion of ready set is employed here.Precise statements are given relating the various semantics in terms of a number of abstraction operators.

A general framework for the denotational treatment of concurrency is introduced. The key idea is the notion of process which is element of a domain obtained as solution of a domain equation in the style as considered previously by Plotkin. We use tools from metric topology as advocated by Nivat to solve this equation, show how operations upon processes can be defined conveniently, and illustrate the approach with the definition of a variety of concepts as encountered in the study of concurrency. Only few proofs of the supporting mathematical theory are given; full proofs will appear in the final version of the paper.