Abstracts of Lectures
on Definability and Computability
Back
to course homepage.
8.3. 2001
Definability in Second Order Logic
Introducing Second Order Logic
Definability of graph theoretic concepts
Many examples
First Order Logic,
Monadic Second Order Logic,
Fragments of Second Order Logic
Undecidability of the consequence problem
15.3. 2001
How to show non-definability?
Ehrenfeucht Fraisse games,
transducers and reductions
22.3. 2001
Finite Automata and Monadic Second Order Logic
FA-recognizable languages, regular languages, MSOL-definable languages
Many examples
B"uchi's Theorem
(also due to Trakhtenbrot, Elgot, Vaught)
What is so special about words?
29.3. 2001
The polynomial hierarchy and Second Order Logic
Characterizing NP (Fagin; Christen)
Characterizing the polynomial hierarchy PH (Meyer, Stockmeyer)
Characterizing P (Graedel)
5.4. 2001
Characterizing P and (non)-deterministic logarithmic space
Fixed point Logic
Transitive closures
The Immerman-Vardi theorem
PESACH
19.4. 2001
Invariant definability and P/poly
Yom Atzmaut
3.5. 2001
First Order Definability in Arithmetic, I
Addition and Order
Decidability of Presburger Arithmetic
Definability of Multiplication
10.5. 2001
First Order Definability in Arithmetic, II
Diophantine definability
Matyasevich's theorem
17.5. 2001
First Order Definability in Arithmetic, III
Proof of Matyasevich's theorem
24.5. 2001
What is so special about First order Logic?
Completeness and
Compactness Theorem
Loewenheim-Skolem-Tarski Theorem
Characterizing First Order Logic (Lindstroem)
31.5. 2001 *
Tarski Centenary
7.6. 2001
Definability over the Real Numbers
Tarski's theorem on Elimination of Quantifiers
14.6. 2001
Computability over the Real Numbers
Blum-Shub-Smale model of Computation
21.6. 2001
The millenium problem
P =? NP over various fields
What have we learnd concerning P=?NP