une sorte de crise existentielle de la communauté internationale mathématique
vers 1880 : apogée de la théorie des ensembles¶
La théorie des ensembles (ensembles, relations, fonctions ...) est très prolifique, en particulier en Allemagne.
Elle est utilisée dans toutes les branches des mathématiques.
 |
L'élève sérieux "Les ensembles sont au top" "La diagonale, c'est de la balle" |
| Georg Cantor |
 |
Le logicien anglais "Y a un truc qui cloche ..." |
| Bertrand RUSSELL |
$x \in E \Leftrightarrow x \notin x$¶
$E \in E \Leftrightarrow ...$¶
Une affirmation équivalente à sa négation ?? Ne serait-on pas entrain de faire n'importe quoi ?
 |
Le chef "Ça suffit les paradoxes !" "Les maths, c'est du sérieux !" "Nul ne doit nous exclure du Paradis que Cantor a créé." |
| David Hilbert |
1900-1928¶
Hilbert précise petit à petit son idée ...
1928 - Programme de Hilbert :¶
... pour aboutir à un programme de recherche, afin de fonder de nouvelles mathématiques :
- cohérentes : impossibilité de démontrer une proposition et son contraire
- complètes : pour tout énoncé ou son contraire doit pouvoir être démontré
- "décidables" : disposer d'une procédure de décision (algorithme ?) permettant de tester si un énoncé est vrai ou faux
1931 : Théorème d'incomplétude de Gödel¶
 |
Le petit jeune "il y a des énoncés indémontrables" "Na !" |
| Kurt Gödel |
... Première déception pour le programme de Hilbert¶
| |
Le chef "je suis désappointé ..." |
| David Hilbert |
1930-1936 - Calculabilité¶
Hilbert souhaitait "disposer d'une procédure de décision permettant de tester si un énoncé est vrai ou faux"
("Entscheidungsproblem" ou "problème de la décision"), c'est-à-dire
Créer un "mécanisme" de démonstration automatique (un algorithme).¶
- En entrée : un énoncé mathématique
- En sortie : Vrai ou Faux
Ce qui soulève une autre question ...
Qu'est-ce qui peut être calculé par un machine ?¶
C'est la notion de calculabilité.
Problème auxquels s'attaquent, Alan Turing et Alonzo Church, chacun de leur côté
Deux modèles de calcul :¶
Alan Turing : la machine de Turing¶
- a inspiré les ordinateurs actuels (CPU, Ram)
Alonzo Church : le $\lambda$-calcul¶
- a inspiré les langages de programmation fonctionnels (fonctions, composition de fonctions ...)
Formellement, une machine de Turing est un quintuplet $(Q,\Sigma,q_0,F,\delta)$ où :
- $Q$ est un ensemble fini d'états ;
- $\Sigma$ est l'alphabet de travail des symboles de la bande, contenant $\bullet$ un symbole particulier (dit blanc)
- $q_0$ est l'état initial de la machine;
- $F$ est l'ensemble des états finaux (ou acceptants) de la machine;
- $\delta : Q \times \Sigma \rightarrow \Sigma \times \{\leftarrow, \rightarrow, \downarrow\} \times Q$ est la fonction de transition de la machine
$\delta(q,s)=(s',depl,q')$ signifie :
- la machine étant dans l'état $q$, et la tête de lecture étant sur le symbole $s$
- écrit sur la bande le symbole $s'$ (à la place du $s$)
- déplace la tête de lecture dans le sens de la flèche ($\leftarrow$ : vers la gauche, $\rightarrow$ : vers la droite, $\downarrow$ : reste sur place)
- passe dans l'état $q'$,
exemple de machine de Turing :¶
cf Exercices
NB : ça ressemble beaucoup à un "super"-automate ...
NB : les automates et leur formalisme apparaissent plus tardivement (environ 1950)
Le $\lambda$-calcul¶
Système de réécritures symboliques¶
Une $\lambda$-expression $e$ est soit :
- $x$ : une variable
- $\lambda x.e$ : une fonction qui à $x$ associe $e$
- $e_1 e_2$ : l'application d'une fonction $e_1$ à une expression $e_2$
Exécution d'un calcul :
- $(\lambda x.e)\,\, e' \leadsto e[x\leftarrow e']$ : appliquer une fonction à une expression consiste à substituer les occurrences de $x$ par $e'$
exemple de $\lambda$-calcul :¶
cf Exercices
NB : ça ressemble beaucoup à de la programmation purement fonctionnelle
Démontré par Turing, lorsque devenu étudiant de Church
Hypothèse de Church-Turing¶
... et on ne peut pas calculer quoi que ce soit de plus ?
aucun modèle de calcul n'a pour l'instant apporté quoi que ce soit de plus¶
Modèle Turing-complet¶
modèle Turing-complet = aussi puissant qu'une machine de Turing
sont Turing-complets :
- un ordinateur moderne (CPU + Ram)
- un langage de programmation avec boucle while ou récursivité (Python, C, OCaml, ...)
- ...
Raisonner sur la calculabilité¶
On pourra donc considérer de manière équivalente :
- une machine de Turing
- une $\lambda$-expression
- un algorithme décrit en pseudo-code,
- un programme C / OCaml / Python ...
- une suite de caractères représentant le code source d'un programme
- une fonction OCaml / ...
Turing :¶
Il n'existe pas de machine prenant en entrée une machine $M$ et une entrée $e$, et décidant si l'exécution de $M$ sur $e$ termine
NB : machine universelle¶
Turing a dû définir une machine dite machine universelle permettant de simuler l'exécution d'une autre machine passée en entrée
si on considère qu'une machine correspond à un programme :
- on a donc un programme (universel) qui simule l'exécution d'un autre programme
- c'est un interpréteur (par exemple l'interpréteur Python)
| |
Le chef "je suis re-désappointé ..." |
| David Hilbert |
L'idée d'une machine/programme qui permet d'exécuter une machine/programme¶
- ordinateur moderne (machine qui lit et exécute un programme)
- interpréteur (programme qui lit et exécute un programme)
- machines virtuelles (programme qui simule une machine)
La démonstration automatique (idée initiale de Hilbert)¶
- sujet actif de recherche encore aujourd'hui