Home
Scholarly Works
Computability of Operators on Continuous and...
Journal article

Computability of Operators on Continuous and Discrete Time Streams

Abstract

A stream is a sequence of data indexed by time. The behaviour of natural and artificial systems can be modelled by streams and stream transformations. There are two distinct types of data stream: streams based on continuous time and streams based on discrete time. Having investigated case studies of both kinds separately, we have begun to combine their study in a unified theory of stream transformers, specified by equations. Using only the standard mathematical techniques of topology, we have proved continuity properties of stream transformers. Here, in this sequel, we analyse their computability. We use the theory of computable functions on algebras to design two distinct methods for defining computability on continuous and discrete time streams of data from a complete metric space. One is based on low-level concrete representations, specifically enumerations, and the other is based on high-level programming, specifically ‘while’ programs, over abstract data types. We analyse when these methods are equivalent. We demonstrate the use of the methods by showing the computability of an analog computing system. We discuss the idea that continuity and computability are important for models of physical systems to be “well-posed”.

Authors

Tucker JV; Zucker JI

Journal

Computability, Vol. 3, No. 1, pp. 9–44

Publisher

SAGE Publications

Publication Date

January 1, 2014

DOI

10.3233/com-14024

ISSN

2211-3568

Contact the Experts team