Convergence indécidable

[Galuel]

Je me suis essayé Voici le résultat :

Soit une méthode algorithmique définie, M, (composée de tous les groupes de méthodes connues M1, M2, M3, …, Mn) permettant de déterminer si des suite (Un) quelconques, convergent ou non, en donnant pour résultat M(U) = respectivement 1 ou 0
Soit G la suite de nombres dont les k premiers termes sont algorithmiquement définis comme suit:


1°) k = 0 ; G0 = 0
2°) G_k+1 = G_k + M(G)
3°) Ajouter 1 à k et retour en 2°)

Qu’en est-il de M(G) ?

Si M estime que G converge alors M(G) = 1 et les termes de G seront tous définis par G_k+1 = G_k + 1, ce qui implique que G diverge. Ce qui est contradictoire.


Si M estime que G diverge alors M(G) = 0 et les termes de G seront tous définis par G_k+1 = G_k, ce qui implique que G converge. Ce qui est aussi contradictoire.


M ne peut donc aboutir à une conclusion définitive qui par construction remettrait en cause la nature même de G.

La convergence de G est donc indécidable par M

Conclusion : quel que soit l’état des méthodes de résolution de convergence connues, il existe toujours des suites de nombres dont la convergence ne peut pas être déterminée par ces méthodes.


Creative Common by Ḡaluel (version originale sur ḡlibre)
-----

[Amanuensis]

La suite n'est pas définie. Ce qui montré est

"supposons qu'il existe une suite G telle que G(k+1) - G(k) = M(G), alors on obtient une contradiction"

C'est un simple raisonnement par l'absurde, dont la conclusion en logique usuelle est la non existence de la suite G.

[Galuel]

Non M est un programme, qui, à une entrée, constituée par un fichier (considérée comme une définition de suite) donne 1 ou 0 en sortie.

Pour l'ensemble des suites à méthodes résolution connue M donne 1 ou 0 de façon efficace.

On construit cette suite G par l'algorithme ainsi défini que M prend en entrée à chaque étape, donc il ressort 0 ou 1 à chaque étape.

Cette série n'est ni convergente ni divergente selon M il se contredira en permanence. cf Omega de Chaitin pour un principe très proche.

[invite6a7dc6d5]

Bonsoir , vous dite que G(k+1)=G(K)+M(G) alors que ce n'est autre que G(k+1)=G(k)+1 et rien d'autre car comme état de départ de la suite G elle contient qu'un nombre fini de terme donc elle converge vers le dernier terme définie , votre fonction M(G) est mal définie car tu définie au même Temp une suite convergente et après tu définie ça croissance de façon divergente , c'est toi qui a définie la contradiction , cordialement Fazoumar

Ps : corriger moi si j'ai une erreur quelque part ( surtout celle d'orthographe )

[A voir en vidéo sur Futura]

[Galuel]

votre fonction M(G) est mal définie

M est parfaitement défini, de façon parfaitement indépendante de G. M étant connu et la définition de G étant connue de la même façon, M peut prendre la définition de G en entrée, et donc rendre 0 ou 1 de façon parfaitement définie par la structure même de M.

[gg0]

Bonsoir.

Il y a un problème de base : tes algorithmes rassemblés dans M ne peuvent pas décider pour toute suite de nombres si elle converge. Tout simplement parce qu'on ne connaît pas de méthode permettant de prouver la convergence de n'importe quelle suite. Et l'étude des termes les uns après les autres ne prouve rien : la convergence, c'est à la fin, pas sur les n premiers termes, aussi grand soit n.

Donc tu as traité un faux problème. Dommage, l'argument diagonal aurait pu encore une fois se révéler utile.

Cordialement.

[Galuel]

Il y a un problème de base : tes algorithmes rassemblés dans M ne peuvent pas décider pour toute suite de nombres si elle converge. Tout simplement parce qu'on ne connaît pas de méthode permettant de prouver la convergence de n'importe quelle suite.

C'est une mauvaise approche du problème. M apporte une réponse pour toutes les définitions algorithmiques qu'on lui donne. Et la démonstration consiste à démontrer que forcément M n'est pas complet. La démonstration implique donc que l'on NE PEUT PAS avoir un M complet. Autrement dit affirmer que "l'on ne connaît pas M" n'est pas intéressant ici, puisqu'on démontre que M N'EXISTE PAS (en tant que répondant à TOUTES les suites, mais existe en tant que répondant à un panel connu), ce qui est plus fort.

Et l'étude des termes les uns après les autres ne prouve rien : la convergence, c'est à la fin, pas sur les n premiers termes, aussi grand soit n.

Parler l'étude des termes est inintéressant. Il ne s'agit pas de présupposer la forme de M là encore, puisque la conclusion c'est que M N'EXISTE PAS. Qu'il y aura toujours une définition algorithmique de suite qui échappera à l'analyse de M. M peut être syntaxiquement méta-analytique sur la nature de la définition, et cela n'a rien à voir avec le fait de le connaître ou pas. Quoi que fasse M pour donner sa réponse, aussi puissant soit-il, on peut construire G à partir de M en lui donnant non pas G, mais la définition de G en entrée de M, ce qui donnera les termes de G pour tout k.

Ce qui dont est une définition parfaitement valide de G.

Donc tu as traité un faux problème. Dommage, l'argument diagonal aurait pu encore une fois se révéler utile. Cordialement.

On peut approcher la suite G en lisant Meta Math, "hasard et complexité", ou encore "Omega" de Chaitin. Chaitin a défini la probabilité qu'un programme informatique s'arrête et démontré qu'elle était non-calculable. Ici c'est différent, étant donné les méthodes connues, on sait comment bâtir une suite qui échappe à ces méthodes.

[invite6a7dc6d5]

Si je comprend Bien vous dite que M(G) = 1 ou 0 donc déjà votre processus condamner tous autre suite dont le terme qui suit le G(8)=10 n'est ni 10 ni 11 ? ?
Donc supposent qu'on parle que des suites a pas de 1 au max et a pas de 0 sinon , donc c'est des suite qui converge que si a partir d'un certain ordre le pas et 0

Voila j'ai essayé d’être claire , comme ca si je comprend mal le concept du début tu me réoriente merci

[Galuel]

Si je comprend Bien vous dite que M(G) = 1 ou 0 donc déjà votre processus condamner tous autre suite dont le terme qui suit le G(8)=10 n'est ni 10 ni 11 ? ?

Non. Si M est défini, alors la démonstration est qu'il n'est pas complet.

[invite6a7dc6d5]

j'ai pas compris votre dernière réponse

[Amanuensis]

On construit cette suite G par l'algorithme ainsi défini que M prend en entrée à chaque étape, donc il ressort 0 ou 1 à chaque étape.

Donnez nous les détails et résultats des dix premières étapes.

[gg0]

C'est une mauvaise approche du problème. M apporte une réponse pour toutes les définitions algorithmiques qu'on lui donne. Et la démonstration consiste à démontrer que forcément M n'est pas complet.

1) Il ne suffit pas de parler d'un programme pour qu'il existe.
2) On le sait d'avance que M n'est pas complet.

Et n'importe comment, tu parles de indécidable. Pour un objet non défini.

Je n'irai pas plus loin, si les remarques de bon sens ne sont pas traitées techniquement, c'est que l'on est incompétent.

[Galuel]

Je n'irai pas plus loin, si les remarques de bon sens ne sont pas traitées techniquement, c'est que l'on est incompétent.

Une affirmation risquée, "bon sens" étant relatif et "on" non défini...

On le sait d'avance que M n'est pas complet

Démontre le.

Je n'irai pas plus loin, si les remarques de bon sens ne sont pas traitées techniquement, c'est que l'on est incompétent.

[Amanuensis]

Une affirmation risquée,

Comme ce fil depuis le début, risqué pour celui qui le lance et le défend avec aplomb, mais sans vraiment de munitions.

[Galuel]

Comme ce fil depuis le début, risqué pour celui qui le lance et le défend avec aplomb, mais sans vraiment de munitions.

Un pré-matématicien découvrant la notion de convergence, et ne connaissant que les formes de suite Un = 1/n^p affirme :

"M analyse la forme de définition des suites et affirme que toute suite Un de la forme 1/n^p pour p>1 et toutes les autres suites divergent" M répond donc 1 ou 0 à toute suite qui lui est présentée.

G n'étant pas de cette forme (G0 = 0 suffit à le démontrer pour M) La suite Gp calculée sur la base de M nous donne donc G = {0;0;0;...} une suite constante.

Un autre mathématicien lui faisant remarquer que M dit que G diverge alors que manifestement G est une suite convergente, ce qui implique soit d'invalider G comme suite valide, soit d'invalider M comme étant une méthode s'appliquant à toute définition de suite connue, donc d'étendre la notion de suite à d'autres formes que les formes Un connues.

Et de la même façon, M étant amélioré, toute méthode M répondant "converge ou diverge" à toutes les formes de suites définies qui lui sont données en entrée, se retrouvera face à une suite G devant laquelle il devra faire un choix d'invalidation ou d'extension.

Voici UN exemple de point de départ récursif relatif à l'extension de M.

[invite179e6258]

Non M est un programme, qui, à une entrée, constituée par un fichier (considérée comme une définition de suite) donne 1 ou 0 en sortie.

un fichier éventuellement infini donc.

[inviteea028771]

Démontre le.

Pas besoin, c'est déjà fait, et de façon beaucoup plus générale :
http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Rice

Il n'existe donc pas d'algorithme permettant de savoir si toute suite calculable converge (et donc par extension, toute suite)


D'autre part, la suite G de ton premier message n'est pas forcément bien définie.

Par exemple une variante, avec M(U) = 0 si la suite converge et M(G) = 1 si la suite diverge.

Alors la suite G(n+1) = G(n)+M(G) et G(0) = 0 n'est pas bien définie : G(n) = n, mais aussi G(n) = 0 répondent à la définition

[Galuel]

Pas besoin, c'est déjà fait, et de façon beaucoup plus générale :
http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Rice

Il n'existe donc pas d'algorithme permettant de savoir si toute suite calculable converge (et donc par extension, toute suite)

Eh bien heureusement. Voilà qui n'invalide pas le propos.

D'autre part, la suite G de ton premier message n'est pas forcément bien définie.

Par exemple une variante, avec M(U) = 0 si la suite converge et M(G) = 1 si la suite diverge.

Alors la suite G(n+1) = G(n)+M(G) et G(0) = 0 n'est pas bien définie : G(n) = n, mais aussi G(n) = 0 répondent à la définition

Une autre définition d'autre chose n'invalide en rien.

C'est comme dire que le parallélisme est mal défini en géométrie euclidienne étant donné qu'en géométrie sphérique il y a plusieurs parallèles.

[Galuel]

un fichier éventuellement infini donc.

Non car dans ce cas M ne répond pas 1 ou 0 et donc l'hypothèse de départ n'est pas remplie.

[inviteea028771]

Une autre définition d'autre chose n'invalide en rien.

Prouve donc que ta suite G est bien définie.

Parce que si M(G) n'est pas bien défini, la suite G n'est pas non plus, à priori, bien définie (puisque sa définition fait appel à M(G) )


Il ne suffit pas d'affirmer qu'une chose existe pour qu'elle existe.

[Galuel]

Prouve donc que ta suite G est bien définie.

G est bien définie. Ceci étant démontré pour être cohérent avec G, M ne peut pas prendre n'importe quelle forme. Par ailleurs une forme de M ayant déjà été donnée, il est donc démontré qu'il existe au moins un M cohérent avec G.

Par application du processus d'extension des systèmes cohérents il existe une infinité d'extensions de M cohérente avec G.

[invite179e6258]

annulé (sans intérêt)

[inviteea028771]

G est bien définie.

Quelle est donc la démonstration de l'existence/le caractère bien défini d'une telle suite G ?

Il ne suffit pas d'énoncer des propriétés que doit satisfaire un objet pour que ce dernier existe.

[Galuel]

Quelle est donc la démonstration de l'existence/le caractère bien défini d'une telle suite G ?

J'ai déjà donné un exemple d'existence.