Event Detail

Fri Apr 3, 2015
2 LeConte Hall, 4–6 PM
Alfred Tarski Lectures
Julia Knight (University of Notre Dame)
Computability and complexity of uncountable structures

The first lecture will begin with Tarski’s result on the decidability of the elementary first order theory of the ordered field of real numbers. We will consider sample questions in computable structure theory, on countable structures and relations on these structures. The lecture will include a brief review of tools from computability theory used in measuring complexity of structures. There will be sample results, focusing on those obtained using infinitary formulas of special forms. In the second lecture, we consider questions about classes of countable structures. The lecture will include a brief description of tools for measuring complexity of classes. There will be sample results, again with an emphasis on those obtained using infinitary formulas of special forms. In the third lecture, we consider what computability can say about uncountable structures. The lecture will include recent results comparing the computing power of structures related to the ordered field of reals. For these results, elementary first order theories are important, but infinitary formulas of special forms also appear.