Mathematical logic seminar - October 2, 2002

Computer Scientists often use informal programming languages, known as "pseudocodes", to describe algorithms. Of course, because there are many different computer programming languages, each of which is useful for a different class of practical applications, there are many different pseudocodes.

But Recursion Theory, the branch of Mathematics that gave rise to Theoretical Computer Science, is concerned mainly with algorithms in the abstract. That is, a Recursion Theorist typically is concerned only with the logical structure of algorithms, independent of practical concerns or implementation issues. It is therefore somewhat surprising that there is no universally agreed-upon pseudocode used in Recursion Theory. Instead, most Recursion Theorists rely on a set-theoretic notation which often obscures the algorithmic content of their results.

With these issues in mind, we propose a standard pseudocode for describing the logical structure of algorithms, taking motivation from applications in Generalized Recursion Theory--a traditionally highly set-theoretic branch of Recursion Theory.