Introduction to Formal Logic and Computation

Project Description

The project Logic and Computation was aimed at introducing the field of Modern Logic and Theory of Computation. Logic is the study of the way in which we reason and the various very general ways in which we prove things. Axiomatisation, which was originally a concept given by Euclid, in his treatise on Geometry. The properties of Axiomatisation were carefully examined and formally put in the later years. Notions of completeness and soundness of a system of axioms began to be studied. Finally coming to David Hilbert, a Mathematician in the early 20th Century. He started a program to find a set of axioms that could prove every statement that is true(Completeness) and not be able to prove every statement that is false(Soundness). In all this, enters Godel, who geniusly proved that such an axiomatization is not possible for all statements about the natural numbers, forget about statements related to other things. Godel uses a blend of techniques namely, Godel’s Recursive functions, Godel Numbering, Representation theory ending with a very unexpected proof by contradiction.

Computation is a notion everyone has an idea of, using mechanisms to carry out computational tasks. A very simple abstract model of a computing device is the finite automata, capable of solving decision problems, with the class of all decidable problems(languages) being called Regular Languages. It turns out that finding out whether some problem can be solved by the automata or not becomes a more interesting problem than solving a problem, and that is the basis of idea of classifying problems into complexity classes. A simple but strong enough model of computing devices is the Turing machine model (given by Alan Turing) supposed to be able to compute any problem that can be done by any physically realizable computing device. This model provides a good basis for classifying problems based on their solvability as well as hardness. It gives rise to various complexity classes, the two most fundamental being P and NP, yet so tricky to understand ‘completely’ that whether P = NP has been a long-standing unsolved problem.

Mentors

  • Udit Narayan Pandey :- Computation
  • Dawood Bin Mansoor:- Logic
  • Ayush Kumar:- Logic

Learning Roadmap

The project was divided into two halves. The content of the lectures was organised to keep the mentees interested and the exercises were designed to keep them involved. First Logic was taught in the following order:

  • Propositional Logic( Semantics)
  • Propositional Logic( Syntactics)
  • Predicate Logic( Semantics)
  • Predicate Logic( Syntactics)
  • First Order Theory and Other Miscellaneous Things

Each section was dedicated a week but due to difficulties some sections took more time. Every week we would meet, the entire reading material given for the last week was explained again, and I would then give them the reading material and assignment for the next week. In the second half, we started with the basics and went on to study the two classes P and NP in the order:

  • Computation, finite automata and Regular Languages
  • Turing machines, computational complexity, undecidability and reduction
  • P, Non-deterministic Turing machines, NP and a discussion on P vs NP

Resources

For the logic part we used:The reading material was from Dr. Mohua Bannerjee’s Lectures in the course MTH302. For the computation part: We prepared pdf lecture notes and exercises based on the content from the books- Michael Sipser’s Introduction to the Theory of Computation and Arora, Barak’s Computational Complexity: A modern Approach. We also input some ideas of our own.

The resources can be accessed from the resources folder : here