You are here

LINGI 1123 - Computability and complexity

Prof. Yves Deville ( )
Teaching assistant: Michael Saint-Guillain ( )

Main themes and learning outcomes

  • Computability : problems and algorithms, computable and non computable functions, reductions, undecidable classes of problems (Rice), fix point theorem, Church-Turing thesis
  • Main computability models : Turing machines, recursive functions, lambda calculus, automates
  • Complexity theory : complexity classes, NP-completeness, Cook’s theorem, how to solve NP-complete problems

Students completing successfully this course will be able to

  • recognize, explain and identify the limits of computing science
  • explain the main computability models especially their foundations, their similarities and their differences
  • identify, recognize and describe non computable and untractable problems

Students will have developed skills and operational methodology. In particular, they have developed their ability to

  • have a critical look at the performance and capabilities of computer systems

Course content

  • Introduction
  • Concepts: demonstration and reasoning, sets, Cantor’s diagonalization
  • Computability: basic results
  • Models of computability
  • Analysis of the Church-Turing thesis
  • Introduction to computational complexity
  • Complexity classes
Course image: