Suite de Specker

Ernst Specker en 1982 (coll. MFO).

Une suite de Specker est un contre-exemple dans les mathématiques constructives à certains théorèmes établis dans l'analyse classique. Il s'agit d'une suite de nombres rationnels qui est calculable, croissante, et majorée, mais dont la limite n'est pas un nombre réel calculable, ce qui (en mathématiques constructives) contredit le théorème de la limite monotone. Ces suites furent découvertes en 1949 par le mathématicien zurichois Ernst Specker (1920-2011).

Exemple 1

Soit A un ensemble d'entiers naturels récursivement énumérable mais non récursif. Il est l'image d'une suite calculable injective (k_n). La suite de Specker associée est définie par

$\forall N\in \mathbb {N} \quad x_{N}=\sum _{n\leq N}2^{-{k_{n}}}.$

C'est bien une suite calculable de rationnels, croissante et majorée, dont la limite est le réel non calculable :

$x_{A}=\sum _{k\in A}2^{-k}.$

Exemple 2

Une suite de Specker. Le n-ième chiffre de x_n+k est 4 si le calcul de {n}(n) est fini après k étapes ; sinon 3.

On peut donner le développement décimal des nombres dans une suite de Specker (x_m) à partir d'une énumération quelconque des machines de Turing. La n-ième décimale de x_m est un 4 si m > n et le calcul de {n}{n}, c'est-à-dire, l'action de la n-ième machine de Turing sur le numéro n, aura fini après m – n étapes. Si elle n'a pas fini après m – n étapes (ou si m < n), c'est un 3.

• Chaque x_m est un nombre rationnel, puisqu'il a un développement décimal périodique : après les m premières décimales, les chiffres sont tous des 3.
• La suite est calculable, parce que, ayant calculé x_m, pour produire x_m+1 on n'a qu'à effectuer le calcul de m + 1 machines de Turing pour une étape chacune.
• La suite est croissante, car en passant de x_m à x_m+1 les chiffres ne peuvent que changer de 3 à 4.
• La suite est majorée, car elle ne dépasse jamais 0,4444444… = 4/9.
• La limite de cette suite n'est pas un réel calculable, puisque son développement décimal contient 4 à sa n-ième place si le calcul de {n}(n) termine, et 3 sinon, ce qui est une représentation du problème de l'arrêt.