TY - GEN
T1 - Final algebras, cosemicomputable algebras, and degrees of unsolvability
AU - Moss, Lawrence S.
AU - Meseguer, José
AU - Goguen, Joseph A.
PY - 1987/1/1
Y1 - 1987/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84935366841&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84935366841&partnerID=8YFLogxK
U2 - 10.1007/3-540-18508-9_25
DO - 10.1007/3-540-18508-9_25
M3 - Conference contribution
AN - SCOPUS:84935366841
SN - 9783540185086
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 158
EP - 181
BT - Category Theory and Computer Science, Proceedings
A2 - Pitt, David H.
A2 - Poigne, Axel
A2 - Rydeheard, David E.
PB - Springer
T2 - International Conference on Category Theory and Computer Science, 1987
Y2 - 7 September 1987 through 9 September 1987
ER -