No Cover Image

Journal article 591 views 72 downloads

Computability of Operators on Continuous and Discrete Time Streams / John Tucker; Jeffrey I Zucker

Computability, Volume: 3, Issue: 1, Pages: 9 - 44

Swansea University Author: Tucker, John

DOI (Published version): 10.3233/COM-14024

Abstract

A stream is a sequence of data indexed by time. The behaviour of natural and artificial systems can be modelled bystreams and stream transformations. There are two distinct types of data stream: streams based on continuous time and streamsbased on discrete time. Having investigated case studies of b...

Full description

Published in: Computability
Published: 2014
Online Access: http://content.iospress.com/articles/computability/com024
URI: https://cronfa.swan.ac.uk/Record/cronfa21548
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: A stream is a sequence of data indexed by time. The behaviour of natural and artificial systems can be modelled bystreams and stream transformations. There are two distinct types of data stream: streams based on continuous time and streamsbased on discrete time. Having investigated case studies of both kinds separately, we have begun to combine their study in aunified theory of stream transformers, specified by equations. Using only the standard mathematical techniques of topology, wehave proved continuity properties of stream transformers. Here, in this sequel, we analyse their computability. We use the theoryof computable functions on algebras to design two distinct methods for defining computability on continuous and discrete timestreams of data from a complete metric space. One is based on low-level concrete representations, specifically enumerations, andthe other is based on high-level programming, specifically ‘while’ programs, over abstract data types. We analyse when thesemethods 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”.
Keywords: analog computing, computing on streams, many-sorted algebras, topological algebras, stream operators, synchronous concurrent algorithms
College: College of Science
Issue: 1
Start Page: 9
End Page: 44