Computability and Definability, 236331

Spring 2008

Last update May 14, 2008

Last given: Spring Semester 2005/6

Lecturer: Prof. J.A. Makowsky (Taub 628, janos@cs, 4358)
Reception hour: Monday 14:30-16:00
and by appointment via e-mail.

Tutorials: T. Kotek
Reception hour: By appointment via e-mail.

Time: Thursday 09:30-12:30 (Lecture and Tirgul)
NOTE: On the average 1/3 of the course are tirgulim. But we will freely choose when to hold tirgulim and announce it in time.
For the first two weeks we have 3 hours of lectures.
Place: Taub 8

Updated (15. May 2008): Announcements and lectures of 2008,

Announcements and lectures of 2006,

General View

Definability deals with the expressive power of description languages which are used in program specification, databases and axiomatic mathematics. These languages include Regular Expressions, First Order Logic, Relational Algebra, Second Order Logic and various Temporal and Modal Logics.
Computability deals with computations and the resources needed to execute them in various models of computations. These include Finite Automata, Turing Machines, Register Machines, and the like.
The course deals with the interplay between definability in various descriptive languages and computability with various computing devices. It brings together theoretical aspects of Database Theory, Computability Theory, Complexity Theory and Logic.

Why should one take this course?

For the undergraduate and graduate students alike, the course lays the groundwork for a better understanding of the foundations of Computer Science. The course will also bring the student into a field of active research and we shall suggest several topics for further M.Sc. and Ph.D. work.

Prerequisites and Format:

Logic and Sets for CS (234293) , Computability (236343);
2 hours and 1 hour exercices; project; 3 points;
Graduates and undergraduates.

Grading

Students are required to do some homework and 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.

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