Algebra Seminar talk
2016-04-08
Dino Rossegger (DMG, TU Wien)
Computable Structure Theory
Abstract:
The notion of Turing reducibility is probably the most important notion in computability theory; it allows us to measure the algorithmic content of sets of natural numbers. But how to measure the algorithmic content of notions, theorems, and constructions in other areas of mathematics? This is the goal of computable structure theory, or computable model theory as it is often called.
The talk is an introduction to computable structure theory. I will briefly review the required computability theoretic and model theoretic notions and will then focus on a classical approach to measure the algorithmic content of structures, the notion of degree spectra. This property, first studied by Knight and Richter in the eighties has since become one of the best studied notions in the field. I will present the most important results on degree spectra and give proof sketches to some of them so the listener can get an idea how such results are proved.
If time permits I will also briefly talk about a related notion, the notion of computable dimension.
To follow this talk it is beneficial to possess basic knowledge in computability theory and model theory.