Computability and Definability, 236331
Winter 2004/5
(Under construction, last update Oct 18, 2004)
Last given: Spring Semester 2001
Lecturer: Prof. J.A. Makowsky (Taub 628, janos@cs, 4358)
Reception hour: Monday 16:00-18:00
Tutorials: J.A. Makowsky
Reception hour: 16:00-18:00
Time:
Tuesday 12:30-14:30 (Lecture)
and
Tuesday 10:30-11:30 (Tirgul)
Place: TAUB 401
Prerequisites and Format:
Logic 1 ,
Computability (236343);
2 hours and 1 hour exercices; project; 3 points;
Graduates and undergraduates.
Grading
Students are required to do a project, which consists in
summarizing material of the course and additional articles
and bring them into presentable form. The option of a
take--home exam remains open.
General View
The course deals with the interplay between definability
in various descriptive langauges and computability with various
computing devices.
It brings together theoretical aspects of Database Theory,
Computability Theory, Complexity Theory and Logic.
The course will bring the student into a field of active research
and we shall suggest several topics for further M.Sc. and Ph.D.
work.
Syllabus
-
Finite structures and the
undecidability of
the tautology problem over finite structures.
-
Ehrenfeucht Games, definability and non--definability results.
-
Second Order Logic and its fragments:
Fixed Point Logic, etc.
Translation schemes and reducibilities.
-
Logical characterization of complexity classes.
-
Is P=?NP a logical problem ?
-
Lindstrom's theorem characterizing First Order Logic
on arbitrary structures.
References,
Web master: janos@cs.technion.ac.il