Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Cours 2.33.3

2.33.3 Computing over the reals: models, computability, complexity (24h, 3ECTS)

Responsable: Olivier Bournez, Professeur Ecole polytechnique.

Thursday, from 12h45 to 15h45.

Room 1004.

Motivations et objectifs du cours

This course is discussing computability and complexity theory for computations over the real numbers.

Pre-requisites

Basic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...)

Course Description

We will introduce various way to model and discuss computations over the real numbers:

For example:

* Computable analysis: a real is seen as a sequence of converging rational numbers, and one considers Turing machines transforming rational sequences into rational sequences

* Continuous time models of computation: what can be computed using analog electronics, circuits?

Course Language

English upon request. French by default.

Messages :

Messages: * The first lecture is on Thursday 16th September 2021

* No lecture on November 4th 2021

VERSION 2021

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

* Lecture 2:

  • Computable analysis: computable functions (see consolidated pdf below)
  • Course notes: Chapter 4 and 5 of pdf below.

* Lecture 3:

  • Computable analysis: representing spaces of functions, subsets. Intermediate value theorem (see consolidated pdf below)
  • Course notes: Chapter 6 and 7, 8 of pdf below.

* Lecture 4:

  • Computable analysis: Intermediate value theorem. Complexity. Some selected results
  • Course notes: Chapter 8, 9 and 10 of pdf below.

part I

Bibliography for 4 first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, an the excellent “Tutorial: Computability & Complexity in Analysis” on this web page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

* Lecture 5:

  • Static indecidability. Example of Richardson Theorem
  • Dynamic undecidability. Computing with PCD and PAM

* Lecture 6:

  • The General Purpose Analog Computer (GPAC)
  • GPAC-generable functions and closure properties
  • Simulating a Turing Machine with GPAC-generable functions in discrete time

part II (updated)

BELOW IS THE PAGE OF 2018

Course content in 2018 (2021 will be different) :

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

  • Computable analysis: computable reals. (see consolidated pdf below)

* Lecture 2:

  • Computable analysis: computable functions (see consolidated pdf below)

* Lecture 3:

  • Computable functions: oracle view. Modulus of continuity.
  • Computable subsets.

* Lecture 4:

  • Intermediate Value Theorem
  • Complexity

* Lecture 5:

  • Selected results
  • Complexity

* Lecture 6:

* Lecture 7:

  • Computing with dynamical systems with non-necessarily rationals coefficients
  • Space/time contractions for PCD Systems

* Lecture 8:

Course notes :

Course notes:

See course above.

Bibliography (Edition 2018-2019) :

Bibliography for first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, et l'excellent “Tutorial: Computability & Complexity in Analysis” sur cette page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

Relevant Courses (version 2018)

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA