Computability and Definability, 236331
Fall 202122
Last update: July 01, 2021
Previous update: July 01, 2021
Summary of given lectures
Course homepage:
http://www.cs.technion.ac.il/~janos/COURSES/23633121/
Last given: Winter Semester 201819
Lecturer: Prof. J.A. Makowsky (Taub 628, janos@cs, 4358)
Reception hour: By appointment via email.
Tutorials: Prof. J.A. Makowsky
Lecture: Thursday, 9:3011:30
Tirgul: Thursday, 11:3012:30
Place: TBC. Facetoface or ZOOMmeeting if required.
Announcements and lectures of 202122,
Previous announcements (also useful for NOW) :
Announcements and lectures of 201516,
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 :
Due to the changes in the courses listed below, the old prerequisites are not enforced.
However, some knowledge of basic logic and computability
will be helpful. We assume familiarity with Turing machines.
Old prerequistes were:
Logic and Sets for CS (234293) ,
Computability (236343);
Format:
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
takehome exam remains open.
Syllabus

Finite structures and the
undecidability of
the tautology problem over finite structures.

Ehrenfeucht Games, definability and nondefinability 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