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 Ernst Specker (de).
Une suite de Specker. Le
ne chiffre de x
n+k est
4 si le
calcul de {n}(n) est fini après
k étapes; sinon
3.
Exemple
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 ne décimale de xm est un 4 si m>n et le calcul de {n}{n}, c'est-à-dire, l'action de la ne machine de Turing sur le numéro n, aura fini après (m-n) étapes. S'il a 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 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 calculable, puisque son développement décimal contient 4 à sa ne place si le calcul de {n}(n) termine, et 3 sinon, ce qui est une représentation du problème de l'arrêt.
Sources
- (de) Ernst Specker, « Nicht konstruktiv beweisbare Sätze der Analysis », dans J. Sym. Logic (en), vol. 14, no 3, septembre 1949, p. 145-158
- (en) Boris Kushner (en), Lectures on Constructive Mathematical Analysis, AMS, 1984 [lire en ligne] (traduit du russe)
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Suite de Specker de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Oméga de Chaitin — Un nombre Oméga de Chaitin est une suite de bits représentant, sous forme concentrée, la solution du problème de l arrêt pour tous les programme d une machine de Turing universelle donnée. En théorie algorithmique de l information, une constante… … Wikipédia en Français
Théorème de la limite monotone — Le théorème de la limite monotone est un théorème d analyse, la branche des mathématiques qui est constituée du calcul différentiel et intégral et des domaines associés. Sommaire 1 Énoncé pour les fonctions 2 Énoncé pour les suites 3 … Wikipédia en Français
Groupe abélien libre — En mathématiques, un groupe abélien libre est un groupe abélien qui possède une base, c est à dire une partie B telle que tout élément du groupe s écrive de façon unique comme combinaison linéaire à coefficients entiers d un nombre fini d… … Wikipédia en Français
Le Mans Sarthe Basket — Le Mans Sarthe Basket … Wikipédia en Français
Sporting Club Moderne Le Mans — Le Mans Sarthe Basket Le Mans SB Club fondé en 1939 … Wikipédia en Français
Liste der Biografien/Sp — Biografien: A B C D E F G H I J K L M N O P Q … Deutsch Wikipedia
André Buffière — Fiche d’identité Nationalité … Wikipédia en Français
Axiome De Fondation — L axiome de fondation, encore appelé axiome de régularité, est l un des axiomes de la théorie des ensembles. Introduit par Abraham Fraenkel, Thoralf Skolem (1922), et John von Neumann (1925)[1], il joue un grand rôle dans cette théorie, alors que … Wikipédia en Français
Ernst Specker en 1982
