Computability theory is the mathematical theory of
algorithms. (See computability
theory
home page.) Problems which can be solved
algorithmically are called decidable. Undecidable
problems can be more precisely classified by
considering generalized algorithms, which require
external knowledge. Turing degrees provide an
important measure of the level of such knowledge
needed. Computable model theory explores algorithmic
properties of objects and constructions arising within
mathematics.

I am especially interested in computability theoretic
complexity of relations (see Hirschfeldt's
Bulletin of Symbolic Logic paper) and structures
(see Harizanov's
Bulletin of Symbolic Logic paper), including
their Turing degrees. I am also interested in quantum
computing and in theoretical computer science, in
particular, complexity theory, frequency computations,
and inductive inference and algorithmic learning
theory. My other interests include natural language
semantics and philosophy of mathematics.

My research has been supported by the NSF research
grants DMS-1202328
(2012–2015), DMS-0904101 (2009–2012), DMS-0704256
(2007–2009), and DMS-0502499 (2005–2007), as well as
by the NSF binational research grants for
collaboration with Russia/Kazakhstan (2000–2014).

Logic
Colloquium, European Summer Meeting of the
Association for Symbolic Logic, Evora, Portugal,
July 2227, 2013. Member of the Program Committee.
Co-organizer (with Felix
Costa) of the Special Session on
Computability.