Master TAL - MSc. NLP

Course Unit

Calculability and complexity







Course Description

In this course, we study the principal concepts of calculability and algorithmic complexity. After having introduced Turing machines as a principal model of calculation - as well as the properties of these machines (universality, non-determinisme, k-band machines, and Church-Turing thesis) – we study the existing non calculable functions (and undecidable problems). This will emphasize the power classical models and their efficiency due to reduced calculations. We also introduce the notion of complexity measurement (space and time) and the classes of distinct complexities (P, PSPACE, NP, EXPTIME, …).


Learning Outcome

  • Modeling of a Turing machine problem
  • Identification of complexity of an algorithmic problem


  • UE 701

Targeted Skills

  • Analyse a problem before computationally treating spoken or written data
  • Know how to put into place algorithmic techniques, linguistic analysis, statistics, and knowledge processing
  • Develop an argument with critical thinking skills


Pierre Monnin


More Informations


  • To be completed

Course URL – Arche

  • To be completed

Link with other courses

  • to be completed

Evaluation procedures

Number of Tests

  • 1

Nature of the tests

  • final exam

Group work

  • to be completed

Combine with other specialization

  • No

Back to MSc Sciences Cognitives

Back to Master TAL - MSc. NLP