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[2] (1920-2011).

Ernst Specker en 1982 (coll. MFO[1]).

Exemple 1

modifier

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

 

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

 

Exemple 2

modifier
 
Une suite de Specker. Le n-ième chiffre de xn+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 (xm) à partir d'une énumération quelconque des machines de Turing. La n-ième décimale de xm 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 xm 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é xm, pour produire xm+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 xm à xm+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.

Notes et références

modifier
  1. Autres photos.
  2. (de) Ernst Specker, « Nicht konstruktiv beweisbare Sätze der Analysis », J. Sym. Logic, vol. 14, no 3,‎ , p. 145-158.
  3. Cf. (en) Klaus Weihrauch, Computable Analysis : An Introduction, Springer, , 288 p. (ISBN 978-3-540-66817-6, lire en ligne), p. 5 ou (moins facile à lire) (en) Boris Kushner (en) (trad. du russe), Lectures on Constructive Mathematical Analysis, AMS, (lire en ligne), p. 129-130.