Wei Jiang:   MSc, Dec. 2002.
Universality and Semicomputability of Non-deterministic Programming Languages over Abstract Algebras.

Abstract. 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 deterministic While programs, which serves as a foundation for much of my work.

My research involves the extension of this work to the nondeterministic programming languages WhileRA consisting of While programs extended by random assignments, as well as sublanguages of WhileRA formed by restricting the random assignments to booleans or naturals only. The semantics of WhileRA still follows algebraic operational semantics; however, semantic computation trees replace the computation sequences used in the deterministic case, and many-valued semantic functions take the places of those one-valued accordingly.

There are two topics of investigation:

  1. We see to what extent the UFT holds over abstract algebras in these languages.

  2. We investigate concepts of semicomputability for these languages, and see to what extent they coincide with semicomputability for the deterministic While language.