TITLE

Specifiability and computability of functions by equations
on partial algebras.

ABSTRACT

The aim of this research is to compare and contrast specifiability 
and computability of functions on many-sorted partial algebras A
by systems of equations and conditional equations.

As our model of computability, we take the system muPR*(A) 
of primitive recursive schemes over A with added array sorts
and the "mu" (least number) operator.  We show:

(1) Any muPR*-computable function is specifiable (i.e. uniquely
definable) by a finite set of conditional equations over A, 
using either Kleene's semantics, or a "strict" semantics,
for the equality relation between partially defined terms;
but not conversely, i.e, not all conditionally equationally
specifiable functions are computable.

(2) If however we replace "unique definability" by "definability 
as a minimal solution" in Kleene equational logic, and if we
consider only equations, not conditional equations, then we
obtain the class of functions ED*(A), which is shown to be equal to muPR*(A).  
This equivalence provides added support for a Generalised
Church-Turing Thesis.  However the class CED*(A) of minimal
solutions of conditional equations goes beyond muPR*(A) computability.  
In fact such functions are in muPR*(A,eq), i.e., muPR* over A
extended by the equality operator at all sorts.