Theories, classical and uncomplemented

Michael Johnson – 27 September 2023

This talk is inspired by JS Lemay's talk of two weeks ago, and it starts where JS finished (富士山に一度も登らぬ馬鹿に、二度登る馬鹿 -- sometimes translated as "a wise man climbs Mount Fuji at least once, he who climbs it twice is a fool"). We describe a Morita equivalence theorem for theories with "partial algebras" which is analogous to the second of JS's equivalences (no specific memory of JS's talk, or indeed of old Japanese sayings, is required for this talk), and then trace how it led to new "uncomplemented" theories and their applications to computation. Along the way, we'll thread in several comments ("prejudices") about the nature of computation in the hope of clarifying some of the discussions from two weeks ago.