Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Hiérarchie de croissance rapide
Résumé
En théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes fα : N → N (où N est l'ensemble des entiers naturels {0, 1, ...}, et α est un ordinal inférieur à un certain ordinal dénombrable généralement très grand). Un exemple fondamental est la hiérarchie de Wainer, s'étendant à tous les α < ε0. De telles hiérarchies donnent un moyen naturel de classer des fonctions calculables d'après leur vitesse de croissance et leur complexité algorithmique ; elles permettent également d'exprimer de très grands nombres, tels que ceux produits par les suites de Goodstein, lorsque même la notation des flèches chaînées de Conway n'y suffit plus.
Soit μ un grand ordinal dénombrable tel que, pour chaque ordinal limite α inférieur à μ, soit donnée une suite fondamentale, c'est-à-dire une suite strictement croissante d'ordinaux ayant pour limite α. On définit alors une hiérarchie de fonctions fα : N → N, pour α < μ, de la manière suivante :
si α est un ordinal limite.
Ici, fαn(n) = fα(fα(...(fα(n))...)) désigne la nème itérée de fα appliquée à n, et α[n] le nème élément de la suite fondamentale choisie pour l'ordinal limite α.
La partie initiale de cette hiérarchie, formée des fonctions fα d'indice fini (c'est-à-dire avec α < ω), est souvent appelée la hiérarchie de Grzegorczyk en raison de sa relation étroite avec la hiérarchie d'ensembles de fonctions définie par lui, comme on le verra plus loin.
Généralisant encore la définition précédente, une hiérarchie d'itération est obtenue en prenant pour f0 n'importe quelle fonction strictement croissante g : N → N telle que g(0) > 0.
Pour des ordinaux limites inférieurs à ε0, il y a une définition naturelle des suites fondamentales, comme on le verra plus bas dans la description détaillée de la hiérarchie de Wainer, mais pour des ordinaux plus grands, la définition devient beaucoup plus compliquée, demandant par exemple l'utilisation des suites fondamentales de la hiérarchie de Veblen.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.