Final algebras, cosemicomputable algebras, and degrees of unsolvability

Lawrence S. Moss, José Meseguer, Joseph A. Goguen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper studies some computability notions for abstract data types, and in particular compares cosemicomputable many-sorted algebras with a notion of finality to model minimal-state realizations of abstract (software) machines. Given a finite many-sorted signature Σ and a set V of visible sorts, for every Σ-algebra A with co-r.e. behavior and nontrivial, computable V-behavior, there is a finite signature extension Σ′ of Σ (without new sorts) and a finite set E of Σ′-equations such that A is isomorphic to a reduct of the final (Σ′, E)-algebra relative to V. This uses a theorem due to Bergstra and Tucker [3]. If A is computable, then A is also isomorphic to the reduct of the initial (Σ′, E)-algebra. We also prove some results on congruences of finitely generated free algebras. We show that for every finite signature Σ, there are either countably many Σ-congruences on the free Σ-algebra or else there is a continuum of such congruences. There are several necessary and sufficient conditions which separate these two cases. We introduce the notion of the Turing degree of a minimal algebra. Using the results above prove that there is a fixed one-sorted signature such that for every r.e. degree d, there is a finite set E of Σ-equations such the initial (Σ, E)-algebra has degree d. There is a two-sorted signature Σ0 and a single visible sort such that for every r.e. degree d there is a finite set E of Σ-equations such that the initial (Σ, E, V)-algebra is computable and the final (Σ, E, V)-algebra is cosemicomputable and has degree d.

Original languageEnglish (US)
Title of host publicationCategory Theory and Computer Science, Proceedings
EditorsDavid H. Pitt, Axel Poigne, David E. Rydeheard
Number of pages24
ISBN (Print)9783540185086
StatePublished - Jan 1 1987
Externally publishedYes
EventInternational Conference on Category Theory and Computer Science, 1987 - Edinburgh, United Kingdom
Duration: Sep 7 1987Sep 9 1987

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume283 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherInternational Conference on Category Theory and Computer Science, 1987
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Final algebras, cosemicomputable algebras, and degrees of unsolvability'. Together they form a unique fingerprint.

Cite this