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 deterministic While programs. This paper investigates the extension of this work to the nondeterministic programming languages While~(RA) consisting of While programs extended by random assignments, as well as sublanguages of While~(RA) formed by restricting the random assignments to booleans or naturals only. It also investigates the nondeterministic language GC of guarded commands. There are two topics of investigation: (1) the extent to which the UFT holds over abstract algebras in these languages; (2) concepts of semicomputability for these languages, and the extent to which they coincide with semicomputability for the deterministic While language.