Abstract Computability, Algebraic Specification and Initiality

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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; and (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 R 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 define precisely the computable functions.
To appear in ACM Transactions on Computational Logic (57 pages; AMSTeX)

Keywords

Logic in Computer Science, F.1.1;F.3.1;F.4.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30727

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0109001
 http://arxiv.org/abs/cs/0109001

Collections

arXiv