Home
Scholarly Works
Computable total functions on metric algebras,...
Journal article

Computable total functions on metric algebras, universal algebraic specifications and dynamical systems

Abstract

Data such as real and complex numbers, discrete and continuous time data streams, waveforms, scalar and vector fields, and many other functions, are fundamental for many kinds of computation. In the theory of data, such data types are modelled using topological, or metric, many-sorted algebras and continuous homomorphisms. A theory of such topological data types is needed to answer the general questions:1.What are the computable functions on topological algebras?2.What methods exist to axiomatically specify functions on topological algebras?3.Can all computable functions be specified?Such a theory seems to be in its infancy: there are many approaches to computability theory on general and specific spaces, and few approaches to specification theory. In some earlier papers, we have studied the questions 1 and 2 with the needs of data type theory in mind, and built a bridge between computations and specifications to try to answer 3. In this paper, we extend and combine several of our results, to prove new theorems that(i)show the equivalence of some six deterministic or non-deterministic models of computation on various metric algebras and, in particular, on spaces Rn of real numbers;(ii)provide finite universal algebraic specifications for all the functions that can be computably approximated on metric algebras and, in particular, on Euclidean n-space Rn;(iii)show the existence of finite universal algebraic specifications of computably approximable finite dimensional deterministic dynamical systems.A technical issue is the localisation of uniform continuity using exhaustions of open sets. We use specifications composed of conditional equations, inequalities and, for convenience, new exhaustion primitives, that define functions uniquely up to isomorphism.

Authors

Tucker JV; Zucker JI

Journal

The Journal of Logic and Algebraic Programming, Vol. 62, No. 1, pp. 71–108

Publisher

Elsevier

Publication Date

January 1, 2005

DOI

10.1016/j.jlap.2003.10.001

ISSN

1567-8326

Contact the Experts team