Suite de Specker
# Suite de Specker

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

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.
