Suite de Specker

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

${\displaystyle \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[3] :

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

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.