Calculabilité

Nom : Entier-e
Entrée :
    n : un entier
Programme :
    si n vaut 0
        rendre e
    sinon:
        rendre 0

C'est bien un algorithme puisque :

• sa description est finie pour tout e
• son temps d'exécution est fini pour tout n

Il suffit d'utiliser l'algorithme de la division de deux entiers décimaux appris en primaire.

On doit cette preuve magnifique au mathématicien allemand Georg Cantor. Elle est basée sur l'argument s'appelant diagonale de Cantor.

On commence en remarquant que l'on peut associer à tout entier $i$ formé des chiffres $c_1\dots c_k$ le réel de représentation décimale $0.c_1\dots c_k$, ce qui démontre qu'il y a au moins autant de réels dans $[0, 1]$ que de nombres entiers.

On suppose ensuite qu'il existe une injection $f: [0, 1] \rightarrow \mathbb{N}$ entre les réels de l'intervalle $[0, 1]$ et les entiers. On peut alors classer tous les réels avec leurs valeurs selon $f$ :

• on appelle $r_1$ le 1er réel, c'est-à-dire celui tel que $f(r_1) \leq f(x)$, quel que soit $x \in [0, 1]$
• on appelle $r_2$ le second réel, c'est-à-dire celui tel que $f(r_2) \leq f(x)$ pour tout $x \in [0, 1] \backslash \{ r_1 \}$
• ...
• on appelle $r_i$ le $i$ème réel : $f(r_i) \leq f(x)$ pour tout $x \in [0, 1] \backslash \{ r_1, \dots, r_{i-1} \}$
• ...

Chaque réel pouvant s'écrire sous sa représentation décimale (par exemple $0.1034842$), on construit le nombre réel $r$ de $[0, 1]$ tel que son $i$ème chiffre après la virgule soit :

• $1$ si le $i$ème chiffre après la virgule de $r_i$ est différent de $1$
• $2$ si le $i$ème chiffre après la virgule de $r_i$ est $1$

Le nombre $r$ est bien dans $[0, 1]$ mais il ne peut pas être $r_i$ quel que soit $i$ ! Il y a une contradiction (comme notre nombre ne finit ni par 9 ni par 0 il a un unique développement décimal et apparaît donc forcément dans notre liste). Notre hypothèse est fausse : il ne peut exister d'injection entre les réels de l'intervalle $[0, 1]$ et les entiers.

Il y a donc strictement plus de réels dans $[0, 1]$ que d'entiers.

On a vu qu'il existait au plus un nombre dénombrable de programmes, donc au plus autant de programmes que de nombres entiers. Il ne peut y avoir d'injection associant à chaque réel son algorithme.

Comme $u_n$ converge vers $x$, pour tout $i> 0$, il existe $N_i$ tel que $\mid x - u_n\mid < 10^{-i}$ pour tout $n > N_i$. Si l'on veut calculer la $i$-ème décimale de $x$, il suffit de calculer $u_{max(i, N_{i})}$ et de prendre sa $i$-ème décimale.

La preuve est identique à celle du Théorème montrant qu'il y a strictement plus de réels que d'entiers.

Comme les fonctions $\widetilde{k}: \mathbb{N} \rightarrow \mathbb{N}$ définies telles que $\widetilde{k}(x) = k$ pour tout $x$ sont deux à deux différentes lorsque $k$ parcourt $\mathbb{N}$, on en déduit qu'il existe au moins autant de fonctions $f: \mathbb{N} \rightarrow \mathbb{N}$ que d'entiers. On suppose alors qu'il y en a autant, donc qu'il existe une bijection entre les fonctions $f: \mathbb{N} \rightarrow \mathbb{N}$ et les nombres entiers.

On peut alors numéroter chaque fonction $f_0$, $f_1$, $\dots$, $f_n$. Cet ordre nous permet de construire la fonction $g: \mathbb{N} \rightarrow \mathbb{N}$ telle que $g(i) = f_i(i) + 1$ pour tout $i \in \mathbb{N}$. Mais ceci est impossible puisque $g \neq f_i$ pour tout $i$ ($g(i) \neq f_i(i)$ par définition de $g$) : il existe strictement plus de fonctions $f: \mathbb{N} \rightarrow \mathbb{N}$ que d'entiers.

Soit $k$ le $\operatorname{pgcd}$ de $a$ et $b$ : $k$ est le plus grand entier tel que $a = k \cdot a'$ et $b = k \cdot b'$ avec $a'$ et $b'$ entiers.

Si $a = b$ on a bien $k = a = b$ et si $a > b$ on a :

Ce qui prouve que $\operatorname{pgcd}(a, b) \leq \operatorname{pgcd}(a-b, b)$. Réciproquement :

Donc $\operatorname{pgcd}(a-b, b) \leq \operatorname{pgcd}(a, b)$ ce qui conclut la preuve.

Si $a$ et $b$ sont deux entiers positifs et tels que $\min(a, b) > 0$ alors : $\max(a, b) - \min(a, b) < \max(a, b) \geq 0$. Il arrivera donc forcément un moment où $\min(a, b) = 0$.

On suppose que $\tau(x, y, z)$ existe pour tous $x, y, z \in \mathbb{N}$. On montre le résultat par récurrence sur $x+y+z= k$.

Si $x+y+z=0$, on a $x=y=z=0$ et $\tau(0, 0, 0) = 0$, la récurrence est vérifiée. On suppose la récurrence vraie pour $x+y+z=k$.

Pour $x+y+z=k+1$, on analyse tous les cas possibles :

• $x \leq y$ : Ok
• $x > y$ et $y \leq z$ : On a $\tau(x, y, z) = \tau(\tau(x-1, y, z), \tau(y-1, z, x), \tau(z-1, x, y))$ :
  • on a $y-1 \leq z$ donc (par hypothèse de récurrence) $\tau(y-1, z, x) = z$
  • soit $x-1 > y$ et $y \leq z$ et alors (par hypothèse de récurrence) $\tau(x-1, y, z) = z$ : $\tau(x, y, z) = \tau(z, z, ?) = z$
  • soit $x-1 \leq y$ et alors (par hypothèse de récurrence) $\tau(x-1, y, z) = y$ : $\tau(y, z, ?) = z$ (puisque $y \leq z$)
• $x > y > z$ : On a $\tau(x, y, z) = \tau(\tau(x-1, y, z), \tau(y-1, z, x), \tau(z-1, x, y))$
  • on a $z-1 < y< x$ et donc $\tau(x, y, z) = \tau(\tau(x-1, y, z), \tau(y-1, z, x), x)$
  • on procède de même que précédemment en analysant tous les cas :
    • $x-1 > y$ et $y-1>z$ : $\tau(x, y, z) = \tau(x-1, x, x) = x$
    • $x-1 > y$ et $y-1=z$ : $\tau(x, y, z) = \tau(x-1, z, x) = x$
    • $x-1 = y$ et $y-1>z$ : $\tau(x, y, z) = \tau(y, x, x) = x$
    • $x-1 = y$ et $y-1=z$ : $\tau(x, y, z) = \tau(y, z, x) = x$

On va encore une fois le prouver par récurrence sur $x+y+z= k$.

Si $x+y+z=0$, on a $x=y=z=0$ et $\tau(0, 0, 0) = 0$ en 0 récursion puisque $x \leq y$, la récurrence est vérifiée. On suppose la récurrence vraie pour $x+y+z=k$.

Pour $x+y+z=k+1$, on analyse tous les cas possibles :

• $x \leq y$ : Ok en 0 récursion

• $x > y$ et $y \leq z$ : On a $\tau(x, y, z) = \tau(\tau(x-1, y, z), \tau(y-1, z, x), \tau(z-1, x, y))$. Par hypothèse de récurrence $\tau(x-1, y, z)$, $\tau(y-1, z, x)$ et $\tau(z-1, x, y)$ existent et ne peuvent valoir (exercice précédent) que :

  • $\tau(y-1, z, x) = z$
  • soit $x-1 > y$ et $y \leq z$ et alors (par hypothèse de récurrence) $\tau(x-1, y, z) = z$
  • soit $x-1 \leq y$ et alors (par hypothèse de récurrence) $\tau(x-1, y, z) = y$

  On a alors soit $\tau(x, y, z) = \tau(z, z, ?)$, soit $\tau(x, y, z) = \tau(y, z, ?)$ ce qui donne sans nouvelle récursion $\tau(x, y, z) = \tau(z, z, ?) = \tau(y, z, ?) = z$ (on a $y \leq z$).

• $x > y > z$ : On a $\tau(x, y, z) = \tau(\tau(x-1, y, z), \tau(y-1, z, x), \tau(z-1, x, y))$. Par hypothèse de récurrence $\tau(x-1, y, z)$, $\tau(y-1, z, x)$ et $\tau(z-1, x, y)$ existent et ne peuvent valoir (exercice précédent) que :

  • $\tau(z-1, x, y) = x$
  • $x-1 > y$ et $y-1>z$ : $\tau(x, y, z) = \tau(x-1, x, x)$. Comme $x-1 \leq x$ on a $\tau(x, y, z) = x$ sans nouvelle récursion.
  • $x-1 = y$ et $y-1>z$ : $\tau(x, y, z) = \tau(y, x, x)$. Comme $x > y$ on a $\tau(x, y, z) = x$ sans nouvelle récursion
  • $x-1 > y$ et $y-1=z$ : $\tau(x, y, z) = \tau(x-1, z, x)$. On a $x-1 > z$ et $x > x-1$, on est ramené au cas précédent ($x > y$ et $y \leq z$) qui converge avec une récursion en plus
  • $x-1 = y$ et $y-1=z$ : $\tau(x, y, z) = \tau(y, z, x)$. On a $y > z$ et $x > y$, on est ramené au cas précédent ($x > y$ et $y \leq z$) qui converge avec une récursion en plus.

En rangeant tous les textes possibles par ordre lexicographique : d'abord les textes à 1 caractère, puis les textes à 2 caractères, etc. on va forcément trouver l'algorithme trivial qui donne une réponse. Parmi tous les textes plus petits ou égaux à l'algorithme trivial (le nôtre possède, on l'a vu $\log_{10}(n) + 42 + 2$ caractères), il y en a un nombre fini, on peut en extraire tous les programmes (facile, ce sont les textes qui veulent dire quelque chose algorithmiquement) et notre algorithme minimum est dedans.

Supposons que la complexité de Kolmogorov soit calculable. Notons Kolmogorov(n) un algorithme la calculant et $K$ le nombre de caractères de celui-ci.

On peut alors définir l'algorithme sans paramètre suivant :

n = 0
tant que Kolmogorov(n) < K + 1000:
    n = n + 1
affiche n à l'écran

Ce programme (de 75 caractères, caractère "aller à la ligne" compris) est bien un algorithme car :

• Kolmogorov(n) est un algorithme
• il y a un nombre infini de nombres mais seulement un nombre fini d'algorithmes sans paramètres ayant moins de $K + 1000$ caractères : il existe forcément un nombre qui n'est pas la sortie d'un algorithme sans paramètre de moins de $K + 1000$ caractères.

Le retour de cet algorithme sans paramètre est le plus petit nombre de complexité de Kolmogorov plus grand que $K + 1000$. Mais ceci est impossible puisqu'il est déterminé par notre algorithme qui fait, en lui concaténant l'algorithme de Kolmogorov(n) pour qu'il soit indépendant, bien moins de $K + 1000$ caractères.

Notre hypothèse de départ est donc fausse : la complexité de Kolmogorov n'est pas calculable.