MATH 5900 Mathematical Logic and Applications
Study of syntax and semantics in first order languages. Analysis of the theorems of Completeness, of Löwenheim-Skolem, of Compactness and the limitations of the formal method. Introduction to the theory of computability by means of Turing machines. Analysis of the theory of numbers and recursive functions, including the theorem of Rice and that of Recursion. Introduction to the complexity theory.