Suite de Specker

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ernst Specker en 1982

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 Ernst Specker (de)[1].

Exemple 1[modifier | modifier le code]

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

\forall N\in\N\quad x_N=\sum_{n\le 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[2] :

x_A=\sum_{k\in A}2^{-k}.

Exemple 2[modifier | modifier le code]

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 énumeration 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. S'il a n'a pas fini après (mn) é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 places, les chiffres sont tous 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 | modifier le code]

  1. (de) Ernst Specker, « Nicht konstruktiv beweisbare Sätze der Analysis », J. Sym. Logic (en), vol. 14, no 3,‎ septembre 1949, p. 145-158
  2. (en) Klaus Weihrauch, Computable Analysis: An Introduction, Springer,‎ 2000 (ISBN 978-3-540-66817-6, lire en ligne), p. 5