Computability and Definability, 236331
Last given: Winter Semester 1997/8
Lecturer: Prof. J.A. Makowsky (Taub 628, janos@cs, 4358)
Reception hour: Monday 14:30-16:30
Assistent: Julian Marino (Taub 619, julian@cs, 4873)
Reception hour: to be announced
Time:
Thursday 09:30-11:30
and
Thursday 11:30-12:30 (Targil)
Place: Taub 5
More information via http:
Click here
http://www.cs.technion.ac.il/~janos/COURSES/CD/announce01.html
Planned abstracts of
lecture . Delays in schedule likely.
Actual course material.
Slides posted in final form AFTER the lectures.
Sorry for possible delays.
Contains also homework, project specifications, and important
ANNOUNCEMENTS.
NEW:
Project proposals
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,
Previous Lecture Notes