Computable Model Theory (13w5047)


(University of Waterloo)

Sergey Goncharov (Sobolev Institute of Mathematics)

(Victoria University of Wellington)

(University of Notre Dame)

(University of California, Berkeley)

(University of California, Berkeley)


The Banff International Research Station will host the "Computable Model Theory" workshop from November 3rd to November 8th, 2013.

Children learn in school how to add and multiply whole numbers, perform long division, and so on. Putting educational development aside, computability theory tells us that this time is wasted: these tasks can be effectively carried out by computers. There are recipes, or emph{algorithms}, that can be mechanically followed by a non-sentient being such as a computer, for performing these computations. However, later in their schooling, students study Euclidean geometry. Rather than mechanically compute, they now require imagination to find proofs for theorems about lines and angles, circles and squares. This time, computability theory delivers a different verdict on the efforts of the educational system: a computer cannot have insight into absolute knowledge of geometry; the human endeavor of finding geometric proofs is inherently creative.

Algebraists generalise the arithmetic operations on whole numbers to construct a plethora of structures. Among them are collections of more complicated numbers, symmetries of mathematical objects, and objects that measure relatedness, such as graphs. The role of computable model theory is to examine these structures and constructions through a computable lens. Which of the algebraic objects can be built by a computer? If they cannot be, what kind of non-computable information (such as all geometric truth) may these objects be coding? When is one structure more complicated than another?

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).