Computability Theory Learning Seminar

Monday, July 11, 2022 1:30 pm - 1:30 pm EDT (GMT -04:00)

Simon Adamus, Department of Pure Mathematics, University of Waterloo

"Punctual Computability Theory"

Punctual computability theory is a relatively new branch of computability theory that deals with punctual structures, a class of structures intermediate between polynomial-time and computable structures. These structures are defined using primitive recursive functions, and we will see that many computable-theoretic notions can be redefined with regards to these functions and be termed "punctual", thus bringing about punctual computability theory. In this series of talks I discuss how this theory compares to computability theory, with a focus on universality. For example, we know graphs are universal for computable structures in the strongest sense, but the scene is quite different in the punctual world.

Knowledge of the material in PMATH 432/632 is assumed.

MC 5403