Conjecture: tentative de lien entre la complexité de Kolmogorov et l'analyse réelle

EtNonLesShills

Le problème a été édité le 03/05

Présentation didactique du problème:


Avec un collègue mathématicien vous êtes force de jouer a un jeu. Alors  au début vous avez le droit de discuter et de vous mettre d'accord sur une fonction   f: mots finis a valeur dans {0;1} -> mot infinis a valeur dans {0;1}. Puis vous ne vous reverrez plus. Le maitre du jeu va alors vous soumettre un mot infini a valeur dans {0;1} mais pas dans $Im(f)$  et vous allez alors donner au maitre du jeu deux mots fini en binaire $m_1$ et $T$. Le maitre du jeu va alors allez voir votre collègue et lui transmettre $m_1$ et $T$, et votre collègue va écrire $f(m_1)$ jusqu'au  Tieme bit. Ensuite on calcul le score, alors déjà si vous collègue a écrit un mot ne commençant pas comme le mot que le maitre du jeu vous a montré (je crois qu'on appelle ca un préfixe) vous perdez directement la partie et allez en enfer, mais un enfer un peu spécial ou vous êtes condamne a écouter la preuve du théorème de Syracuse d'un shtameur jusqu'à la fin des temps. Sinon le score est calculé comme suit:  vous marquez un score égal a la taille du mot écrit par votre collègue auquel on retranche le nombre de bit d'information que vous avez fait transmettre a votre collègue quand vous lui avez fait parvenir $(m_1, T)$ . Le but est alors de trouver la stratégie donnant le score moyen maximal sans ne  jamais perdre.

Présentation formelle du problème avec une solution probablement fausse: 

Definition: Soit $(e_i)_{i\in \mathbb{N}} \in [0;1]^\mathbb{N}$

on définit: 

$f _{ (e_i)_{ i\in \mathbb{ N}}}: [0;1]  \rightarrow\overline{\mathbb{R}}$

$x\mapsto\sup\{-\ln_2(|e_i-x|)-\ln_2(i)-\ln_2((-\ln_2(|e_i-x|)),i\in\mathbb{N}\} $

Théorème (probablement faux mais qui sait...): 

1)Pour tout $(e_i)_{i\in \mathbb{N}} \in [0;1]^\mathbb{N}$  l'intégrale de $f _{ (e_i)_{ i\in \mathbb{ N}}}$ est définie et finie

2) Soit $(k_i)_{ i\in \mathbb{ N}} \in[0;1]^{\mathbb{N}}$ verifiant:
*$Im((k_i)_{ i\in \mathbb{ N}})$ = ensemble des nombres  calculables dans $[0;1]$

* Pour tout $i \leq j : K(k_i) \leq K(k_j)$ ou $K$ est la complexité de Kolmogorov
Soit $(e_i)_{i\in \mathbb{N}} \in [0;1]^\mathbb{N}$ verifiant la suite $(e_i)_{i\in \mathbb{N}}$ est calculable.

alors: $ \int_{0}^{1} f _{ (e_i)_{ i\in \mathbb{ N}}} (x)  \,dx < \int_{0}^{1} f _{ (k_i)_{ i\in \mathbb{ N}}} (x)  \,dx$

Heuristique

Il va falloir écrire ton problème, tes pistes et ton éventuelle solution plus clairement et plus formellement si tu veux une réponse constructive...

EtNonLesShills

Je ne comprends pas en quoi le problème est mal pose ? bon par contre d'accord la piste de solution c'est du café du commerce juste pour me mettre moi au clair sur le chemin a suivre, pas pour rien qu'on a invente le langage mathématique pour faire des maths

il faut que je rédige la preuve mais elle va être longue si rédige bien et triviale

sinon si tant est que ca soit bien vrai que penses tu de l'intégrale de  f comme définition de l'intelligence ?

Heuristique

Pour être plus clair sur ce qui n'est pas clair :

1) "la plus grande réduction d'informations possible sur ce mot à partir de la suite $(e_i)$". Qu'appelles-tu une réduction d'informations ?

2) Le paragraphe commençant par "Pour cela" mériterait que l'on définisse "sur combien de décimales $e_i$ et $y$ coïncident" ou encore la notion de coût.

3) Pour la suite des mots calculables, j'imagine que tu considères des mots infinis (sinon tous sont calculables).

4) Pourrais-tu redéfinir ce qu'est la complexité de Kolmogorov dans ton cadre ?

5) Qu'appelles-tu l'intégrale de $f$ ? Avec quelle mesure travailles-tu ?

Nous avons bien évidemment en tête ce que représente la réduction d'information ou la complexité de Kolmogorov mais remettre des définitions formelles de tout cela ne fait pas de mal. En l'état, les notions que tu utilises, la manière dont tu le fais et ton résultat ne sont pas très claire.

Et si tu essaies de montrer la non calculabilité d'une fonction de Kolmogorov, c'est déjà fait.

EtNonLesShills

alors deja concernant 1) 2) 3) cela concerne l'exposition des motivations mais n'est pas l'enonce du probleme qui debute a "soit plus formelement" ou la je m'efforce de rendre le probleme le plus explicite possible. Je vais neanmoins y repondre

3) *alors comme dit c'est une introduction et ici tu peux considerer que les mots sont finis ou infinis, dans l'enonce du probleme ils sont infinis vu que c'est des nombres de [0;1] mais si tu veux mieux comprendre ce que represente la reduction d'information tu peux considerer dans cette introduction qu'ils sont finis c'est alors plus facile a expliquer/concevoir
* sinon attention potentielle grosse incomprehension ce n'est pas pcq $(e_i)_{i \in \mathbb{N}} $est constitue de mot calculable que $(e_i)_{i \in \mathbb{N} }$ est calculable, ici on ne s'interesse jamais qu'a des (suites de mots) calculables et jamais a des suites de (mots calculable)

1) + 2) La maniere la plus simple de voir les choses (d'ailleurs c'est ce qu'il faut faire au debut de la preuve) c'est de considerer que les mots que l'on cherche a reduire sont finis. Pour cela nous allons trouver une nouvelle representation de ses mots, soit en logique mathematiques une injection h des mots finis dans les mots fini. La nouvelle taille du mot x est alors la taille de la "representation canonique" de h(x). Bon alors maintenant quelle est cette fonction h ?
h: mot fini -> mot fini  x -> (a(x), b(x), c(x))
avec a(x): mot fini -> N x-> l'indice du mot de (e_i) maximisant: [ le nombre nombre de decimal consecutive a partir de la premiere de e_i coincidant avec x ( soit maximisant -ln_2(|x-e_i|) - nombre de bit necessaire pour situe e_i dans la liste des (e_i) (soit ln_2(i)) ]
b(x)  mot fini -> N x-> le nombre de decimale sur lesquelle x et e_a(x) coincide, probablement negligeable
c(x) mot fini -> mot fini x ->x auquelle on a retirer ses premieres decimales ou il coincide avec e_a(x)

on a alors bien une injection, la taille de la nouvelle expression canonique du mot est alors, taille h(x) = taille(a(x))+taille(b(x))+taille(c(x)). Et la reduction d'information c'est (taille initiale de x) - taille h(x), c'est f(x) dans l'enonce, sauf que contrairement a (taille initiale de x) - taille h(x), qui passe pas comme definition quand on parle de mots infinis f(x) elle pas de probleme. et non la notion assez proche qu'il existe un programme tel que pour toute decimale au bout d'un moment le programme tient la bonne decimale mais il ne sait pas quand et il ne s'arrete pas.

 4) bah la complexite de kolomogorov enfin plus exactement une complexite de kolmogorov quelquonque. On fixe une MTU soit m (fini ou infini) calculable K(m) = taille de l'entree minimum s'arretant sur m. Par contre je vais en profiter pour preciser ce que j'entend par mot infini calculable, un mot infini est calculable s'il existe un programme qui pour tout n prenant n en entre s'arrte sur les n premiere decimal de ce mot

5) (a plus de gras, les mystere de l'informatique...) boa mesure/integrale de lesbegue je suppose de tout maniere je connais qu'elle , on a tout de meme une certaine regularite que je detaillerais si t'as envie qui me dit qu'il ya de bonne chance que ca passe. 


Et si tu essaies de montrer la non calculabilité d'une fonction de Kolmogorov, c'est déjà fait je le sais sinon j'aurais pas dit que avec machin utilisant complexite de kolmogorov dans ca definition ca majorait (strictement je pense j'aurais du me mouiller dans l'enonce) tout les machins utilisant calculables


edit: j'avais fait qq fautes

Heuristique

Ne t'inquiète pas, je sais faire la différence entre une "suite de (mots calculables)" et une "(suite de mots) calculable". Tu as écrit "si $(e_i)_{i \in \mathbb{N}}$ est l'ensemble des mots calculables", tu as donc écrit que que tu t'intéressais à une "suite de (mots calculables)".

Pour la suite, tu n'as pas pris le temps de définir les termes de ton énoncé. Tu utilises trop de notions sans les préciser : je t'invite à prendre le temps d'écrire proprement et formellement "Définition 1 : [...]", "Définition 2 : [...]" avec un concept par définition, à la manière des ouvrages de mathématiques, à savoir formellement.

Le résultat de minoration pour Kolmogorov est également parfaitement connu, inutile de s'énerver.

EtNonLesShills

ahi t'inquiètes je m'énerve a cause du gras pas de toi

Le résultat de minoration pour Kolmogorov 

lequel ?

ah un gentil modo l'a enlevé

. Tu as écrit "si (ei)i∈N(𝑒𝑖)𝑖∈𝑁 est l'ensemble des mots calculables"

ah oui oups, euh non pas oups en fait a l'endroit ou c'est,  c'est bien ca ya pas de problème

le gentil modo a aussi catapulter une partie de mon texte ailleurs ahi


bon je l'ai déjà dit l'énonce du problème commence a : Soit plus formellement:, et s'arretes a ... calculable. Il est de ce que je peux en juger parfaitement défini, il ya avant les motivations au problème qui sont bon bah c'est des paramaths et après le chemin extrêmement grossièrement dessiné de la preuve, mais c'est pas l'enoncé

Heuristique

Sur la page wikipédia "Complexité de Kolmogorov" ( https://fr.wikipedia.org/wiki/Complexité_de_Kolmogorov ), on a un résultat de minoration $K_U(x) \leqslant K_M(x) + c_M$ qui décrit un peu ce principe dans les grandes lignes.

EtNonLesShills

oui K indépendante de la machine a une constante près, ca n'a rien a voir avec mon résultat

si vraiment le non formel te dérange, ne te concentres que sur l'énonce et pas ce qu'il y avant ( et surtout pas ce qu'il y a apres oula)

mais je pense ca ira beaucoup mieux quand t'auras une preuve bien carrée (surtout le début de la preuve qui reprend ce que j'explique quand je réponds a tes questions 1+2)

bon allé je commence a la rediger moarfffff, c'est hyper mais alors vraiment hyper chiant a bien rediger

Heuristique

La preuve permet rarement d'éclairer une définition peu formelle... Au contraire, si la définition d'un objet n'est pas formelle alors il ne peut y avoir de preuve.

Je viens de remarquer qu'il fallait effectivement sauter une partie pour comprendre la suite. Dans 2), qu'appelles-tu l'intégrale d'une fonction définie à partir de $(e_i)_{i \in \mathbb{N}}$ calculable ?

EtNonLesShills

1) Heuristique après avoir dormi je vois ce qui peut te poser problème dans l'exposition du problème je vais édit (après avoir poster ce post) et tu peux regarder 4) aussi

2) Malheureusement ma preuve est fausse, je détaillerais pas, mais le style de faux irrécupérable et je doute même fortement maintenant que le résultat soit juste, on peut toujours néanmoins se questionner sur quel $(e_i)_{i\in \mathbb{N}}$ donne une intégrale la plus forte possible 

3) le terme de l'énonce ou je dis que je pinaille de pas le négliger, est non négligeable sinon la fonction devient facilement infinie en quasi tout point, on pourra méditer sur 4) pour s'en convaincre

4) J'ai eu l'idée de poser le problème de manière didactique ca m'a bien aide quand j'y réfléchissais aussi, je pense même que je vais mettre cette version dans le post principal avant la version formalisée.

Avec un collègue mathématicien vous êtes force de jouer a un jeu. Alors  au début vous avez le droit de discuter et de vous mettre d'accord sur une fonction   f: mots finis a valeur dans {0;1} -> mot infinis a valeur dans {0;1}. Puis vous ne vous reverrez plus. Le maitre du jeu va alors vous soumettre un mots infini a valeur dans {0;1} mais pas dans Im(f)  et vous allez alors donner au maitre du jeu deux mots fini en binaire $m_1$ et $T$. Le maitre du jeu va alors allez voir votre collègue et lui transmettre $m_1$ et $T$, et votre collègue va écrire $f(m_1)$ jusqu'au la Tieme bit. Ensuite on calcul le score, alors déjà si vous collègue a écrit un mot ne commençant pas comme le mot que le maitre du jeu vous a montré (je crois qu'on appelle ca un préfixe) vous perdez directement la partie et allez en enfer, mais un enfer un peu spécial ou vous êtes condamne a écouter la preuve du théorème de Syracuse d'un shtameur jusqu'à la fin des temps. Sinon le score est calculé comme suit:  vous marquez un score égal a la taille du mot écrit par votre collègue auquel on retranche le nombre de bit d'information que vous avez fait transmettre a votre collègue quand vous lui avez fait parvenir $(m_1,T)$. Le but est alors de trouver la stratégie donnant le score moyen maximal sans ne  jamais perdre.

pour en revenir a 3) on peut imaginer une variante de ce jeu ou vous donnez juste $m_1$, vous ne pouvez pas perdre et ou votre collègue écrit $f(m_1)$ en entier puis on calcul le score en regardant combien de bit consécutif a partir du premier il a de juste - nombre de bit que vous lui avez transmis, pour quasiment tout fonction $f$ de départ l'espérance est alors infinie.

Heuristique

Ah, je comprends enfin ton problème ! (Petite typo pour ta fonction où tes $y$ sont sûrement des $x$).

Au passage, éditer sans ajout d'un "EDIT : problème modifié" rend la conversation très difficile à suivre pour les lecteurs du fil.

EtNonLesShills

Heuristique a dit :

 (Petite typo pour ta fonction où tes $y$ sont sûrement des $x$).

ah oui oups