Universality and semicomputability for nondeterministic programming languages over abstract algebras

The Universal Function Theorem (UFT) originated in 1930s with the work of Alan Turing, who proved the existence of a universal Turing machine for computations on strings over a finite alphabet. This stimulated the development of stored-program computers.Classical computability theory, including the UFT and the theory of semicomputable sets, has been extended by Tucker and Zucker to abstract many-sorted algebras, with algorithms formalized as …