Les ordinateurs peuvent-ils résoudre tous les problèmes SOLVABLES ?

[invite06fcc10b]

Avis au modérateur :
peut-être est-il préférable de rajouter "solvable" au titre de l'autre fil commençant de façon identique ?

Je rajoute en effet cette question ici, car il me semble que le théorème de Gödel nous dit précisément qu'il existe des formules dont il n'est pas possible de savoir si elles sont vraies ou fausses, c'est indécidable. Et donc, il existe des problèmes insolubles.

En revanche, ce qui est plus complexe, c'est de savoir s'il existe des problèmes solvables qui ne pourraient être résolus par des ordinateurs, c'est à dire qui ne sauraient trouver une solution algorithmique. A priori, les travaux de Church et de Turing permettent de répondre non à cette question.
Néanmoins, une des faiblesses des ordinateurs, c'est de ne pas pouvoir manipuler de vrais nombres réels. En général, il suffit de les approcher par des décimaux avec suffisamment de précision pour que cela ne soit pas gênant dans la résolution du problème. Mais existe-t-il des cas où une telle approximation serait insuffisante ?
-----

[invitebf65f07b]

En général, il suffit de les approcher par des décimaux avec suffisamment de précision pour que cela ne soit pas gênant dans la résolution du problème. Mais existe-t-il des cas où une telle approximation serait insuffisante ?

Oui, une grande sensibilité à ces variations peut faire diverger un calcul...
Je pense en particulier à ce qu'on appelle le chaos déterministe, dont une caractéristique est la sensibilité aux conditions initiales.

Historiquement, Edward Lorenz a constaté cet effet en travaillant sur une simulation "simple" de l'atmosphère. En voulant gagner du temps, il a repris ces calculs informatiques un peu avant là où il s'était arrêté et les résultats obtenus alors n'avaient rien avoir avec le premier calcul... La différence : la machine travaillait avec une précision de 6 chiffres après la virgule, mais n'en affichait que 3. En reprenant le calcul au milieu, il a donc perturbé les valeurs de moins d'un milième... Cette différence s'est très vite amplifiée pour finalement donner des résultats radicalement différents.

Il apparaît donc que la prévision numérique d'un système chaotique n'est pas fiable, que ce soit à cause de l'erreur commise à l'initialisation, mais (et c'est plus fort encore selon moi) à cause de l'erreur commise à chaque itération. Le seul moyen de contourner ce problème serait de disposer d'une mémoire infinie pour stocker chaque réel utilisé et produit. Le problème serait sans doute alors de calculer cette précision infinie (temps infini).

[inviteb64bd4b2]

Je rajoute en effet cette question ici, car il me semble que le théorème de Gödel nous dit précisément qu'il existe des formules dont il n'est pas possible de savoir si elles sont vraies ou fausses, c'est indécidable. Et donc, il existe des problèmes insolubles.

A mon avis Godel, ne dit pas du tout ça . Son théorème d'incomplétude dit que tous ce qui est vrai n'est pas forcément démontrable dans une axiomatique donnée (suffisamment large pour contenir l'arithmétique).

[invite06fcc10b]

A mon avis Godel, ne dit pas du tout ça . Son théorème d'incomplétude dit que tous ce qui est vrai n'est pas forcément démontrable dans une axiomatique donnée (suffisamment large pour contenir l'arithmétique).

C'est bizarre, il me semble que tu dis la même chose que moi qui est je le rappelle "il existe des formules dont il n'est pas possible de savoir si elles sont vraies ou fausses, c'est indécidable" !

Si une formule qui est vraie n'est pas démontrable, comment peut-on être sûr que c'est vrai ? On ne peut pas ! Et donc, elle reste bien vraie ou fausse, non ?
Exemple connu : avant qu'on ne parvienne à démontrer la conjecture de Fermat, personne ne savait si la proposition était vraie ou fausse. Bien entendu, ça marchait pour tous les n > 2 et tous les exemples qu'on a pu imaginé, mais certains chercheurs ont aussi cherché s'il n'y avait pas 1 contre-exemple particulier qui aurait instantanément démontré que la proposition était fausse.

A noter aussi que si une formule vraie ne peut être démontrée, la négation de cette formule est fausse et ne peut être démontrée, non ? Bref, bien que ces nuances fassent réfléchir, il me semble qu'il y a bien équivalence de nos dires.

[A voir en vidéo sur Futura]

[invitedb5bdc8a]

La question ne devrait elle pas être, y a t il des problèmes qu'un être humain peut résoudre et qu'un ordinateur ne peut pas résoudre ?

[spi100]

C'est bizarre, il me semble que tu dis la même chose que moi qui est je le rappelle "il existe des formules dont il n'est pas possible de savoir si elles sont vraies ou fausses, c'est indécidable" !

Si une formule qui est vraie n'est pas démontrable, comment peut-on être sûr que c'est vrai ? On ne peut pas ! Et donc, elle reste bien vraie ou fausse, non ?
Exemple connu : avant qu'on ne parvienne à démontrer la conjecture de Fermat, personne ne savait si la proposition était vraie ou fausse. Bien entendu, ça marchait pour tous les n > 2 et tous les exemples qu'on a pu imaginé, mais certains chercheurs ont aussi cherché s'il n'y avait pas 1 contre-exemple particulier qui aurait instantanément démontré que la proposition était fausse.

A noter aussi que si une formule vraie ne peut être démontrée, la négation de cette formule est fausse et ne peut être démontrée, non ? Bref, bien que ces nuances fassent réfléchir, il me semble qu'il y a bien équivalence de nos dires.

Ca ne semble pas être le point de vue de Alain Connes. Je tire la citation de l'article "Une réalité mathématique archaique précède les concepts" du numéro spécial de la recherche N=20.

Question : En quoi cette réalité archaïque résiste-t'elle au formalisme ?
A. Connes : Les structuralistes n'ont jamais vraimement digéré le théorème de Godel. Pour eux, ce théorème dit simplement que dans un système donné il y aura toujours une proposition indécidable, dont on ne peut pas savoir si elle est vraie ou fausse. Or le théorème de Godel est bien plus méchant que cela. Il dit qu'il y aura toujours une proposition vraie qui ne sera pas démontrable dans le système. Ce qui est beaucoup plus dérangeant

[invite6c250b59]

Avis au modérateur :
peut-être est-il préférable de rajouter "solvable" au titre de l'autre fil commençant de façon identique ?

Non. On essai toujours de minimiser les interventions comme modérateur tant que les rêgles du forum sont respectées. Eventuellement ça peut se faire à la demande de l'auteur du fil, mais certainement pas à la demande de quelqu'un d'autre. /Jiav

et personnellement, je ne suis pas du tout sur qu'il existe des problèmes insolvables. Des problèmes insolvables à l'intérieur d'un système d'axiome donnée, certainement. Mais définitivement insolvable pas sur:

il existe des formules dont il n'est pas possible de savoir si elles sont vraies ou fausses, c'est indécidable.

Si je peux me permettre: en fait l'indécidabilité n'est vrai que à l'intérieur d'un système axiomatique donné, et il est (toujours?) possible d'agrandir le système d'axiome, ce qui permet alors de voir que certaines propositions indécidables dans le système plus petit sont en fait vrai (ou fausse bien sur). Le problème c'est qu'en agrandissant le système d'axiome, on tombe alors sur de nouvelles propositions indémontrables... jusqu'à ce que le système soit encore agrandi (pas sur que "agrandi" soit le bon terme... hésitez pas à me corriger).

Il apparaît donc que la prévision numérique d'un système chaotique n'est pas fiable

Certes, sauf que la différence importante entre un système chaotique et un système de hasard, c'est qu'on peut faire un portrait de phase (en gros: comment les résultats du système d'équation varient en fonction d'eux-même) qui comportera moin de degré de liberté (de dimensions) qu'un système "réellement" hasardeux (en gros: les résultats suivent une forme appelée "attracteur étrange").
Or, il a été démontré que l'attracteur étrange obtenu à partir d'une simulation informatique (comportant des erreurs liées à l'approximation) est le même que celui qui aurait été obtenu sans erreurs d'aproximation.

Alors est-ce que c'est vraiment un problème insoluble, ou plutôt une façon de créer du hasard? Est-ce que le hasard peut-être considéré comme un problème insoluble?

La question ne devrait elle pas être, y a t il des problèmes qu'un être humain peut résoudre et qu'un ordinateur ne peut pas résoudre ?

Pas décrêt spécial, tu es autorisé à ouvrir un nouveau fil

[invitebf65f07b]

Certes, sauf que la différence importante entre un système chaotique et un système de hasard, c'est qu'on peut faire un portrait de phase (en gros: comment les résultats du système d'équation varient en fonction d'eux-même) qui comportera moin de degré de liberté (de dimensions) qu'un système "réellement" hasardeux (en gros: les résultats suivent une forme appelée "attracteur étrange").
Or, il a été démontré que l'attracteur étrange obtenu à partir d'une simulation informatique (comportant des erreurs liées à l'approximation) est le même que celui qui aurait été obtenu sans erreurs d'aproximation.

Alors est-ce que c'est vraiment un problème insoluble, ou plutôt une façon de créer du hasard? Est-ce que le hasard peut-être considéré comme un problème insoluble?

merci je suis au courant
je commençais juste par dire qu'il est illusoire de croire que l'on peut prédire l'état d'un système chaotique au delà d'un certain temps en le simulant. Ceci n'empêche pas de dire des choses pertinentes dessus, même à très long terme, mais il faut revoir les notions qui gardent un sens dans ce cas.

Moi je pensais juste que c'était un bon exemple à la question d'Argyre

En général, il suffit de les approcher par des décimaux avec suffisamment de précision pour que cela ne soit pas gênant dans la résolution du problème. Mais existe-t-il des cas où une telle approximation serait insuffisante ?

Mais merci d'apporter des précisions et des nuances

[spi100]

La question ne devrait elle pas être, y a t il des problèmes qu'un être humain peut résoudre et qu'un ordinateur ne peut pas résoudre ?

Oui ouvre un nouveau fil. Autant je suis convaincu de la non-calculabilité de l'Univers, autant je répondrai oui à ta question. Par exemple le halting problème n'est pas solvable par un algorithme mais un être humain en est tout aussi incapable. C'est assez bien expliqué là http://en.wikipedia.org/wiki/Halting_problem , dans la section "Can human solve the halting problem ?".

Mais attention, ça ne prouve rien sur la calculabilité de l'Univers. Un être humain est incapable d'énumérer une suite de nombres complètement aléatoire mais il peut s'aider d'un phénomène physique aléatoire pour le faire. De même un système artificiel peut le faire, a condition de combiner un algorithme et un oracle (l'oracle utilise un phénomène physique pour générer un nombre aléatoire) : mais la classe des automates "maching de Turing + oracle" ne sont plus algorithmiques, on passe à un niveau supérieur de complexité. C'est bien expliqué là http://en.wikipedia.org/wiki/Oracle_machine (la wikipedia c'est top !).

[invite06fcc10b]

Si je peux me permettre: en fait l'indécidabilité n'est vrai que à l'intérieur d'un système axiomatique donné, et il est (toujours?) possible d'agrandir le système d'axiome, ce qui permet alors de voir que certaines propositions indécidables dans le système plus petit sont en fait vrai (ou fausse bien sur).

Sauf que dans ce cas, il me semble qu'il peut y avoir un doute sur la consistance de la théorie agrandie, car il n'y a aucune assurance que le dernier axiome ajouté ne puisse être violé un jour. Et du coup, toute démonstration dans cette théorie est susceptible d'être invalidée un jour.

Un être humain est incapable d'énumérer une suite de nombres complètement aléatoire mais il peut s'aider d'un phénomène physique aléatoire pour le faire.

A condition que le hasard pur existe, ce qui n'a jamais été démontré et dont je doute l'existence.

A. Connes : Les structuralistes n'ont jamais vraimement digéré le théorème de Godel. Pour eux, ce théorème dit simplement que dans un système donné il y aura toujours une proposition indécidable, dont on ne peut pas savoir si elle est vraie ou fausse. Or le théorème de Godel est bien plus méchant que cela. Il dit qu'il y aura toujours une proposition vraie qui ne sera pas démontrable dans le système. Ce qui est beaucoup plus dérangeant

Je ne pense pas que cela fasse beaucoup avancer le schmilblick. Oui, il existe des propositions vraies indémontrables, mais personne ne peut en exhiber un exemple, puisque justement, il n'existe aucune démonstration ! Et donc, en pratique, A. Connes ne peut nier qu'une proposition de cette catégorie restera vraie ou fausse.
Ce qui me dérange, en réalité, c'est qu'on exploite souvent le théorème de Gödel pour montrer que les ordinateurs sont intrinsèquement limités, alors que l'humain ne le serait peut-être pas.
C'est par exemple la position de Penrose me semble t-il.
Or, ce qui compte, ce n'est pas l'existence théorique de formules vraies indémontrables, non, ce qui compte, c'est bien qu'en pratique, ces formules vraies ne pourront jamais être validées comme vraies ou fausses, et ceci indépendamment de la nature de celui qui tente la démonstration, humain, machine ou extra-terrestre.

[invite6c250b59]

Sauf que dans ce cas, il me semble qu'il peut y avoir un doute sur la consistance de la théorie agrandie, car il n'y a aucune assurance que le dernier axiome ajouté ne puisse être violé un jour. Et du coup, toute démonstration dans cette théorie est susceptible d'être invalidée un jour.

Je ne crois pas. Tu fais la même erreur que moi il n'y a pas si longtemps (i.e. avant que je demande l'avis de nos matheux ) entre inconsistance (la vérité des propositions dans un système d'axiome ne change pas sauf si le système d'axiome est contradictoire) et incomplétude (toutes les propositions faisables dans un système ne peuvent être démontrées).

Oui, il existe des propositions vraies indémontrables, mais personne ne peut en exhiber un exemple, puisque justement, il n'existe aucune démonstration !

Il n'existe aucune démonstration si on reste à l'intérieur du système d'axiomes où la proposition est indémontrable.

Ce qui me dérange, en réalité, c'est qu'on exploite souvent le théorème de Gödel pour montrer que les ordinateurs sont intrinsèquement limités, alors que l'humain ne le serait peut-être pas.

Tout à fait d'accord là-dessus par contre!

[spi100]

A condition que le hasard pur existe, ce qui n'a jamais été démontré et dont je doute l'existence.

Si je comprends bien ton point de vue, dans la Nature le hasard n'existe, la notion de continue n'y a pas vraiment de sens (en référence à une autre discussion). Effectivement vue comme ça il n'y a aucune raison que l'Univers ne soit pas calculable.

[invite8c2a9674]

Il semblerai pourtant que la théorie de la mecanique quantique mette en jeu ce hasard pur...Cependant, il est vrai qu'elle est contesté par certains (Einstein le premier, bien qu'il est contribué à son élaboration...). Etant donné que je crois en cette théorie, je pense que le hasard pur existe dans la nature...

[invite06fcc10b]

Si je comprends bien ton point de vue, dans la Nature le hasard n'existe, la notion de continue n'y a pas vraiment de sens (en référence à une autre discussion). Effectivement vue comme ça il n'y a aucune raison que l'Univers ne soit pas calculable.

Okkham (variante) : "Si on a deux théories qui expliquent toutes deux les faits observés alors on devrait utiliser la plus simple jusqu’à ce que d’autre preuves soient découvertes."

Einstein :
"On devrait tout rendre aussi simple que possible, mais pas plus."

Supprimer le concept de nombre infini et de continuité de toute théorie physique (ce qui est suggéré par de nombreux résultats de la physique, comme je l'ai déjà dit par ailleurs) et supprimer également le "hasard pur" de la MQ (ce qui de toute façon reste très controversé), voilà qui simplifie pas mal le monde réel, non ? Et bien le simple, moi, tant que quelqu'un n'aura pas démontré le contraire, ça me convient !

[spi100]

Okkham (variante) : "Si on a deux théories qui expliquent toutes deux les faits observés alors on devrait utiliser la plus simple jusqu’à ce que d’autre preuves soient découvertes."

Einstein :
"On devrait tout rendre aussi simple que possible, mais pas plus."

Supprimer le concept de nombre infini et de continuité de toute théorie physique (ce qui est suggéré par de nombreux résultats de la physique, comme je l'ai déjà dit par ailleurs) et supprimer également le "hasard pur" de la MQ (ce qui de toute façon reste très controversé), voilà qui simplifie pas mal le monde réel, non ? Et bien le simple, moi, tant que quelqu'un n'aura pas démontré le contraire, ça me convient !

L'hypothèse du continu.

1/ Les théories physiques actuelles qui rendent comptent des phénomènes expérimentaux sont continues.
2/Il est très difficile de résoudre analytiquement une théorie discrète. Par contre les calculs sur le continue sont beaucoup plus simple.

Si j'applique le principe d'Occam je serais donc enclins à considérer que l'Univers est continu.

Le hasard.

1/ Les expériences d'Aspect basées sur les inégalités de Bell, jouent en faveur d'une théorie quantique sans variable cachée. Il existe des arguments invalidant l'interprétation d'Aspect, basés sur les coïncidences fortuites (loop-holes), mais ça n'est pas l'explication la plus probable car justement elles invoquent un grand nombre d'évenements fortuits.
2/ Les théories à variables cachées rendent compte des mêmes résultats que la théorie orthodoxe mais sont beaucoup plus complexes conceptuellement et calculatoirement parlant.

Si j'applique le principe d'Occam, je serais enclins à considérer que le Hasard dans la mesure quantique existe bien.

Conclusion
Le principe d'Occam est une aide à la décision mais en aucun cas n'est un argument scientifique. Je m'en suis servis pour arriver exactement à l'inverse de tes idées.

Il serait AMHA beaucoup plus intéressant que tu nous expliques pourquoi considérer une théorie discrète rend au moins aussi bien compte de l'expérience, que les théories continues. Et quels sont tes arguments pour justifier de l'absence de hasard dans l'univers.

[invite8c2a9674]

Il serait AMHA beaucoup plus intéressant que tu nous expliques pourquoi considérer une théorie discrète rend au moins aussi bien compte de l'expérience, que les théories continues.

Il n'existe aucune theorie qui rend aussi bien compte de la réalité que la theorie de la MQ (a l'echelle atmoque bien sur, cette théorie ne marchant pas à l'echelle macroscopique mais c'est un autre débat), donc, je pense qu'utilisé le principe d'Okkham dans ce cas revient à admettre (en attendant de nouvelles experiences) la MQ...

[invite06fcc10b]

L'hypothèse du continu.
1/ Les théories physiques actuelles qui rendent comptent des phénomènes expérimentaux sont continues.

Premiere nouvelle !
La mecanique quantique, comme son nom l'indique, suggere que beaucoup de proprietes physiques ne peuvent avoir comme valeur que certaines "quantites".
Citez donc 1 seule experience qui permet de penser que quelque chose est continu ? En revanche, il est admis qu'un electron ne peut se placer sur n'importe quelle orbite, ce qui revient a dire que toutes les positions ne sont pas autorisees et que donc le principe de continuite spatiale est invalide dans ce cas. La masse ne peut pas prendre toutes les valeurs possibles, donc la encore, il y a de quoi se poser des questions. Le temps ? C'est egalemet suspect, car il n'est pas possible de dissocier 2 evenements survenant a un meme objet de moins d'une certaine quantite. Une onde ? Hormis le fait qu'il faut qu'elle soit presente a plusieurs endroits (mais en nombre finis de positions), la longueur de l'onde ne peut pas prendre n'importe quelle valeur (par exemple pour les photons emis par effet photoelectrique, ou par transition electronique). Mais ou sont donc les presomptions du continu ?

2/Il est très difficile de résoudre analytiquement une théorie discrète. Par contre les calculs sur le continue sont beaucoup plus simple.

Il ne faut pas confondre la resolution d'un probleme et la nature des choses. Si on a un ensemble fini d'atomes qui composent un objet a peu pres spherique, on peut poser comme hypothese qu'il s'agit d'une sphere continue, proceder a une integration dans le continu pour inferer le volume, et en deduire finalement la force de gravitation. Donc oui, les calculs sont plus faciles a resoudre dans le continu (je n'ose imaginer la prise en compte de tous les atomes pour calculer la force de gravitation), mais tous les physiciens s'accordent pour dire qu'il s'agit d'une approximation du reel. Pour une valeur exacte, il faut bien proceder a la prise en compte de tous les atomes et de toutes leur position.

Le hasard.
1/ Les expériences d'Aspect basées sur les inégalités de Bell, jouent en faveur d'une théorie quantique sans variable cachée. Il existe des arguments invalidant l'interprétation d'Aspect, basés sur les coïncidences fortuites (loop-holes), mais ça n'est pas l'explication la plus probable car justement elles invoquent un grand nombre d'évenements fortuits.
2/ Les théories à variables cachées rendent compte des mêmes résultats que la théorie orthodoxe mais sont beaucoup plus complexes conceptuellement et calculatoirement parlant.

Les inegalites de Bell ne s'appliquent pas si les 2 particules etudiees ne sont en fait qu'un seul et meme objet. Certes, cela pose le probleme de l'existence d'un meme objet a plusieurs endroits, donc remise en cause de la localite, mais cela permet de preserver toutes les theories avec variables cachees non locales. Et donc, il est inutile d'introduire le concept de hasard pur, concept qui a comme implication quasi-religieuse de placer la physique en dehors du champ des mathematiques, car il n'y a aucun moyen mathematique / algorithmique de produire des nombres vraiment au hasard.

Conclusion
Le principe d'Occam est une aide à la décision mais en aucun cas n'est un argument scientifique. Je m'en suis servis pour arriver exactement à l'inverse de tes idées.

Certes, mais encore faut-il se mettre d'accord sur les hypotheses de travail !

Il serait AMHA beaucoup plus intéressant que tu nous expliques pourquoi considérer une théorie discrète rend au moins aussi bien compte de l'expérience, que les théories continues. Et quels sont tes arguments pour justifier de l'absence de hasard dans l'univers.

Voir plus haut !

[spi100]

Premiere nouvelle !
La mecanique quantique, comme son nom l'indique, suggere que beaucoup de proprietes physiques ne peuvent avoir comme valeur que certaines "quantites".
Citez donc 1 seule experience qui permet de penser que quelque chose est continu ? En revanche, il est admis qu'un electron ne peut se placer sur n'importe quelle orbite, ce qui revient a dire que toutes les positions ne sont pas autorisees et que donc le principe de continuite spatiale est invalide dans ce cas.

Bon je ne vais pas prendre ton message en bloc. Tu dis qu'il est admis qu'un electron ne peut se placer sur n'importe quelle orbite.
Je pense que tu veux parler du modèle orbital, et ta compréhension m'en semble un peu erronée.
La probabilité de présence est non nulle partout autour du noyau. Selon l'orbitale considérée, effectivement tu montres que la partie radiale de la densité de probabilité admet un maximum pour une valeur donnée de R, et en moyenne l'electron passe la majorité de son temps à la distance R du noyau (c'est une façon de voir semi-classique, et ça n'a pas énormement de sens car je suppose implicitement que l'electron a une trajectoire). Ces maximums sont assimilés aux positions discrètes dont tu parles. Mais de dire que certaines positions sont moins probables que d'autres, ne veut pas dire que les positions sont interdites.

Le fait que le spectre d'un opérateur soit continu ou discret, ne dépend pas que de la nature de l'opérateur, mais aussi et surtout des conditions aux limites.
Un electron libre confiné dans une boite aura par exemple un spectre energétique discret en 1/L^2 (L la dimension caractéristique de la boite). Mais le même electron non confiné aura un spectre complètement continu.

[inviteb64bd4b2]

Si une formule qui est vraie n'est pas démontrable, comment peut-on être sûr que c'est vrai ? On ne peut pas ! Et donc, elle reste bien vraie ou fausse, non ?

Oui mais elle ne peut pas être vraie et fausse à la fois. Le fait qu'elle soit vraie est indépendant du fait que tu puisses la démontrer. C'est subtile, mais c'est ce Godel à montrer : Il y a une différence entre vrai et prouvable.

[spi100]

Est - ce qu'il y a des réfs pas trop compliquées (web ou bouquins) permettant de s'introduire au théorème de Goedel ?

[inviteb64bd4b2]

Le Théorème de Gödel de Ernest Nagel


Outre la traduction de l'article original de Gödel (1931), ce volume propose deux études propres à le mettre en perspective: La démonstration de Gödel, par Ernest Nagel et James R. Newman; Le champ du signe ou la faillite du réductionnisme, par Jean-Yves Girard.

[invite5fc31084]

je ne suis plus tres bien là.

Qqn pourrait me donner un exemple de qq chose de vrai mais non prouvable?

[spi100]

je ne suis plus tres bien là.

Qqn pourrait me donner un exemple de qq chose de vrai mais non prouvable?

L'hypothèse du continu de Cantor :
Soit X un ensemble, s'il existe une injection de |N dans X, et une injection de X dans |R , alors soit il existe une bijection entre |N et X, soit il existe une bijection de |R vers X. En des termes plus imagés, un ensemble est soit dénombrable, soit continu, mais il n'y a pas d'intermédiaire.

Dans l'axiomatique classique des ensembles (Fraenkel-Zermello) cette hypothèse n'est ni réfutable ni démontrable. On peut alors choisir de l'ajouter ou non aux axiomes de la théorie des ensembles.

[invite06fcc10b]

je ne suis plus tres bien là.

Qqn pourrait me donner un exemple de qq chose de vrai mais non prouvable?

Ca métonnerait que quelqu'un puisse exhiber un exemple, puisque justement il ne peut le démontrer. En PRATIQUE, si on exclut les axiomes qui sont vrais par définition, il y a équivalence entre la liste des propositions vraies et celles qui sont prouvables. En THEORIE, il existe des propositions vraies mais non prouvables, sauf qu'on ne peut savoir lesquelles et donc, en pratique, leur véracité reste incertaine.

[invitedb5bdc8a]

Je vous la remet là: mon cher angus tu l'as écris toi même:

la présente phrase est vraie mais non prouvable.

[spi100]

J'ai trouvé ça là http://www.cnrs.fr/Cnrspresse/math2000/html/math08.htm

Je cite

Tarski a ensuite montré que la complexité de l'ensemble des énoncés vrais était intrinsèquement plus grande que celle des énoncés démontrables. En particulier, aucun procédé algorithmique, aucun automate ne peut répondre à toutes les questions arithmétiques. Ces résultats ont été précisés en 1970 par Julia Robinson et Yuri Matijasevic, qui ont montré l'existence de polynômes à plusieurs variables à coefficients entiers qui n'ont pas de racines entières, bien que cela ne puisse être établi par un programme ou par un algorithme. Intuitivement, le théorème de Robinson-Matijacevic nous dit qu'il y a des polynômes sans racines entières, pour lesquels nous ne pourrions montrer cette absence de racines qu'en essayant toutes les valeurs possibles des variables, ce qui est bien sûr impossible.

Il existe des polynomes à plusieurs variables et à coefficients entiers dont il est possible de montrer qu'ils n'admettent pas de racines entières. Et il est aussi montrer qu'il n'est pas possible de le vérifier algorithmiquement.
Ne serait-ce pas un problème résolu (donc solvable) qu'un ordinateur ( machine de Turing universelle ) ne peut pas résoudre ?

[spi100]

On pourrait aussi ajouter que l'énoncé précédent est vrai mais n'est pas prouvable dans le cadre des machines de Turing.

[inviteb64bd4b2]

En PRATIQUE, si on exclut les axiomes qui sont vrais par définition, il y a équivalence entre la liste des propositions vraies et celles qui sont prouvables.

Godel montre exactement le contraire : la liste des propositions vraies et non prouvables est infinie. Il montre réellement quelles sont vraies mais c'est une démonstration métamathématique qui n'utilisent pas les axiomes du système juste la logique formelle et le fait que l'axiomatique considérée est consistante (non contradictoire).

[invite06fcc10b]

Il existe des polynomes à plusieurs variables et à coefficients entiers dont il est possible de montrer qu'ils n'admettent pas de racines entières. Et il est aussi montrer qu'il n'est pas possible de le vérifier algorithmiquement.
Ne serait-ce pas un problème résolu (donc solvable) qu'un ordinateur ( machine de Turing universelle ) ne peut pas résoudre ?

[QUOTE=Photon]
Godel montre exactement le contraire : la liste des propositions vraies et non prouvables est infinie. Il montre réellement quelles sont vraies mais c'est une démonstration métamathématique qui n'utilisent pas les axiomes du système juste la logique formelle et le fait que l'axiomatique considérée est consistante (non contradictoire).
[/Photon]

Il existe des propositions vraies démontrables par une démonstration qui n'utilise pas les axiomes du système. Si on sort du système et qu'on en prend un autre, effectivement, on peut arriver à démontrer plus de choses, mais puisqu'il y a démonstration, cela reste algorithmiquement "prouvable".
Pour Spi100 : si les auteurs ont "montré qu'ils n'admettent pas de racine entière", c'est qu'ils ont exhibé une démonstration (sinon, personne n'admettrait leur résultat). Et comme leur démonstration s'inscrit dans un certain cadre théorique, peut-être métamathématique comme le dit Photon mais peu importe, alors il existe un algorithme qui permet de faire cette démonstration.
Et ce n'est donc pas le fameux exemple recherché !

la présente phrase est vraie mais non prouvable.

Nous ne sommes pas obligés de te croire sur parole, démontres le ! Si c'est évident pour toi, tu dois pouvoir le justifier en apportant une explication claire. Mais attention, si c'est une démonstration, la phrase sera fausse !
Quoi qu'il en soit, on dérape un peu vers les paradoxes de Russel et cie. De telles formules récursives ne sont ni vraies ni fausses, qu'on soit humain ou machine, leur définition est inappropriée.

[spi100]

Pour Spi100 : si les auteurs ont "montré qu'ils n'admettent pas de racine entière", c'est qu'ils ont exhibé une démonstration (sinon, personne n'admettrait leur résultat). Et comme leur démonstration s'inscrit dans un certain cadre théorique, peut-être métamathématique comme le dit Photon mais peu importe, alors il existe un algorithme qui permet de faire cette démonstration.

Quand tu dis que puisqu'il y a démonstration, il y a algorithme, tu te trompes.
Ce que tu n'arrives pas à comprendre, c'est que la puissance démonstrative des machines de Turing est inférieure à celle de la théorie des ensembles.
Les auteurs ont probablement utilisé des résultats d'analyse pour démontrer leur résultat, puis ont montré que ce n'était pas possible à montrer dans le cadre des machines de Turing.