Complexité des fonctions réelles Comparaison de différentes présentations

Abstract

Il s’agit d’étudier et de comparer différents manières de présenter l’ensemble C[0,1] des fonctions réelles uniformément continues sur l’intervalle [0,1], muni de la norme usuelle : II f II∞ = sup{If(x)I ; 0 ≤ x ≤ 1} Usuellement un espace métrique contient des objets de nature infinie (le paradigme étant un nombre réel définie à la Cauchy), ce qui exclut une présentation informatique (c.-à-d. codée sur un alphabet fini) directe de ces objets. Pour contourner cette difficulté, on procède comme il est usuel pour le corps des réels. ON considère une partie dense Y de l’espace considéré X, qui soit suffisamment simple pour que - Ses éléments puissent être codés comme (certains) mots sur un alphabet fini fixé - La fonction distance restreinte à Y soit calculable (C.-à-d. donnée par une fonction calculable σ : Y x Y x N1 Q avec I dx (x,y) – σ(x,y,n) I ≤ 1/2n L’espace X apparaît alors comme le séparé –complété de Y. On dira que le codage proposé pour Y et la description proposé pour la fonction distance constituent une présentation rationnelle de l’espace métrique X. La question qui se pose ensuite est celle de la complexité des fonctions dans le cas des espaces compacts, la question est nettement plus délicate dans le cas général, car elle renvoie à la complexité des fonctionnelles de type 2 arbitraires. Puis comme exemple d’espace métrique, j’ai étudié différentes présentations de l’ensemble C[0,1] des fonctions réelles uniformément continues sur [0,1] ( présentations que nous notons CKF, Ccb, Cesl, Ccaf, Cw, CSp, Cfrac, CSFrac ) en introduisant le point de vue Uniforme.

Il s’agit d’étudier et de comparer différents manières de présenter l’ensemble C[0,1] des fonctions réelles uniformément continues sur l’intervalle [0,1], muni de la norme usuelle : II f II∞ = sup{If(x)I ; 0 ≤ x ≤ 1} Usuellement un espace métrique contient des objets de nature infinie (le paradigme étant un nombre réel définie à la Cauchy), ce qui exclut une présentation informatique (c.-à-d. codée sur un alphabet fini) directe de ces objets. Pour contourner cette difficulté, on procède comme il est usuel pour le corps des réels. ON considère une partie dense Y de l’espace considéré X, qui soit suffisamment simple pour que - Ses éléments puissent être codés comme (certains) mots sur un alphabet fini fixé - La fonction distance restreinte à Y soit calculable (C.-à-d. donnée par une fonction calculable σ : Y x Y x N1 Q avec I dx (x,y) – σ(x,y,n) I ≤ 1/2n L’espace X apparaît alors comme le séparé –complété de Y. On dira que le codage proposé pour Y et la description proposé pour la fonction distance constituent une présentation rationnelle de l’espace métrique X. La question qui se pose ensuite est celle de la complexité des fonctions dans le cas des espaces compacts, la question est nettement plus délicate dans le cas général, car elle renvoie à la complexité des fonctionnelles de type 2 arbitraires. Puis comme exemple d’espace métrique, j’ai étudié différentes présentations de l’ensemble C[0,1] des fonctions réelles uniformément continues sur [0,1] ( présentations que nous notons CKF, Ccb, Cesl, Ccaf, Cw, CSp, Cfrac, CSFrac ) en introduisant le point de vue Uniforme.