scientific article; zbMATH DE number 3911679

From MaRDI portal
Publication:3687683





[For the entire collection see Zbl 0568.00021.] This paper surveys, unifies, and extends a number of results on induction and computability in the context of an algebraic approach to the semantics of programming. The close relationship between computability, induction, and initiality is emphasized. Highlights of this paper include: a software engineering motivation for the initial algebra approach to data abstraction; a review of many-sorted general algebra, including rules for equational deduction that are sound and complete; simple 'inductive' characterizations of initiality (including generalized Peano axioms); constructions for both initial and final (i.e., minimal) algebra realizations of abstract software modules; and a detailed introduction to computable algebras and their relationship to initiality; finality, and rewrite rules, showing in particular how Gödel numberings arise from initiality, and how equationally defined equality relates to both theorem proving by 'inductionless induction' and computability. The latter permits us to give a purely algebraic characterization of computable algebras: an algebra is computable iff it is a reduct of an initial model of a finite equational equality presentation.




Cited in
(70)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3687683)