Monoids of non-halting programs with tests (Q1646607)

It is customary in the theory of computable functions and programming theory to consider the C-algebras of \textit{F. Guzmán} and \textit{C. C. Squier} [Algebra Univers. 27, No. 1, 88--110 (1990; Zbl 0701.03035)] as algebras of possibly unhalting tests. In order to axiomatize the \texttt{if-then-else} construct over possibly unhalting programs, the authors introduced in [Int. J. Algebra Comput. 27, No. 3, 273--297 (2017; Zbl 1365.68165)] the notion of C-set. A C-set is a pair \((M,S_\bot)\) equipped with an action \(M \times S_\bot \times S_\bot \to S_\bot\) satisfying certain axioms. Here, \(M\) is a C-algebra of tests and \(S_\bot\) is a set of programs with a selected element \(\bot\), the error. The present paper extends this model by including composition of programs and of the programs with tests. The C-set \((M,S_\bot)\) is equipped with an additional action \(\circ: S_\bot \times M \to M\); moreover, the set \(S_\bot\) now is a monoid with zero. The resulting object subjected to appropriate axioms is called a C-monoid. The main result (Theorem 4.1): for a subclass of C-monoids (where M is a so-called ada) obtained is a representation in terms of functional C-monoids.