### Basic Information

The Course Deals With The Interplay Between Definability in Various Descriptive Langauges and Computability With Various Computing Devices. Finite Structures and The Undecidability of The Tautology Problem Over Finite Structures. Logical Characterization of Complexity Classes. Ehrenfeucht Games, Mondefinability and Definability Results. Second-order Logic, Logics With Computable Quantifiers and Predicate Transformers. Lindstrom's Theorem Characterizing First-order Logic On Arbitrary Structures.