Title: Turing Categories
Abstract:
This talk is based on the following papers/notes:
(1) “Introduction to Turing categories” with Pieter Hofstra
(2) “Timed set, functional complexity, and computability” with Boils, Gallagher, Hrubes
(3) “Total maps of Turing categories” with Pieter Hofstra and Pavel Hrubes
(4) “Estonia notes” on my website
Turing categories are the theory of “abstract computability”. Their development followed my meeting Pieter Hofstra. He was in Ottawa at the time and he subsequently joined me as a postdoc. The core theory was developed in Calgary before he returned to Ottawa as a faculty member. Tragically he died earlier this year when there was still so much to do and, indeed, that he had done, but had not published.
Turing categories are important because they characterize computability in a minimal traditional context. These ideas are not original to Pieter and I: De Paola, Heller, Longo, Moggi, and others had all travelled in this terrain before we did. Pieter and I simply took the ideas polished them a bit and moved them a step further on a road which still stretches ahead.
So, the purpose of the talk is to try and explain what all this was about … and what we were striving to accomplish. To do this I have to introduce restriction categories and Turing categories in that context. Then I will describe a family of models which are fundamental to computer science. Finally, I will take a quick look along the road at some open issues.
