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

[spi100]

Je suis aussi d'accord et cette limite est indiscutable. Mais ce qui m'intéresse en fait c'est pour le reste des problèmes: peuvent-ils être résolus par ordinateur ?

En fait la question est mal posé. Dans le mot ordinateur, il y a calculabilité et beaucoup plus.
On aurait pu imaginer d'autres titres à cette discussion.

1/ Le réel est il calculable ?
2/ Le réel est il compréhensible ?
3/ Le réel est il simulable ?
Ces 3 questions ne sont pas équivalentes.

1/ La calculabilité est clairement définie, les limites en sont connues et l'on sait comment aller au-delà : les O-machines de Turing par exemple. Ca n'a rien de très étonnant, ça consiste juste à dire que si tu injectes des connaissances non-algorithmiques dans un algorithme, tu peux aller au delà du simple programme. Il peut par exemple s'agir d'initier un programme avec un nombre complètement aléatoire, générer à partir d'un phénomène physique réputé aléatoire.

2/ La compréhension ne se ramène pas à un simple problème d'arithmétique ou de logique, il s'agit plus d'essayer de sémantiser les phénomènes sans forcemment se restreindre à un seul système logique.

3/Le réel est-il simulable, peut - être et même si l'on admet qu'il n'est pas calculable. C'est le cas si tu considères que le continu a un sens physique et que le hasard existe aussi i.e. la grande majorité des théories physiques.
-----

[spi100]

Je parle des programmes dans la vraie vie.

L'exemple que je te donne est un programme de la vraie vie, tu peux écrire la conjecture des nombres jumeaux et la faire tourner sur ta machine si tu veux.
Mais à nouveau, il ne s'agit pas d'un fil traitant du génie logiciel mais bien de la question de la calculabilité du réel.

[invite73192618]

J'aimerais bien avoir plus de précisions sur les deux premières réponses.

martini_bird serait plus compétent que moi pour te répondre. Il s'agit de la crise des fondements, qui a amenée a un changement de paradigme en mathématique.

La méthode axiomatique s'est imposée et fournit depuis le cadre indispensable au raisonnement mathématique.

C'est dans la partie "Logique et formalisme" sur la FAQ de math . Il me semblait aussi avoir vu un message plus développé spécifiquement pour ça de la part de martini mais je n'arrive pas à le retrouver..

[inviteb7bc207b]

L'exemple que je te donne est un programme de la vraie vie, tu peux écrire la conjecture des nombres jumeaux et la faire tourner sur ta machine si tu veux.
Mais à nouveau, il ne s'agit pas d'un fil traitant du génie logiciel mais bien de la question de la calculabilité du réel.

J'ai des doutes de l'utilité d'une condition d'arrêt de cette forme:
"il existe i > 1 tel que i et i +2 sont premiers".


D'abord l'instruction "il existe" n'existe pas à ma connaisssance

[invite73192618]

clt sur la "vrai vie": ne penses-tu pas qu'il est délicat de dire que la condition d'arrêt n'a pas d'influence en informatique, alors que toute la programmation s'est développée justement avec des ordinateurs qui sont limités à ce point de vue? Crois-tu que, si on avait des ordinateurs quantiques ou autre capables de dépasser la condition d'arrêt, le métier de programeur resterait inchangé?

[inviteb7bc207b]

clt sur la "vrai vie": ne penses-tu pas qu'il est délicat de dire que la condition d'arrêt n'a pas d'influence en informatique, alors que toute la programmation s'est développée justement avec des ordinateurs qui sont limités à ce point de vue? Crois-tu que, si on avait des ordinateurs quantiques ou autre capables de dépasser la condition d'arrêt, le métier de programeur resterait inchangé?

Il ne s'agit pas de "condition d'arrêt" en général en informatique. La limite c'est qu'il est impossible d'écrire un programme H qui détermine si un programme P s'arrête.

Alors où est la limite ? Dans la vraie vie on écrit le programme P et c'est tout. On s'en fout du programme H!

Sinon pour le programmeur son soucis dans la vraie vie n'est pas H mais plutot pourquoi P s'est-il arrêté intempestivement avant de donner un résultat

[spi100]

J'ai des doutes de l'utilité d'une condition d'arrêt de cette forme:
"il existe i > 1 tel que i et i +2 sont premiers".


D'abord l'instruction "il existe" n'existe pas à ma connaisssance

Bon là tu pinailles, je suis sûr que tu es capable d'écrire ça sous forme d'un programme. En C ça donnerait quelque chose du genre :

int p1_est_premier;
int p2_est_premier;
int i, j;

for ( i = 0; ; ++i ) {
p1_est_premier = p2_est_premier = 1;
for ( j = 0; j < i - 1; ++j ) {
/*test si p1 est premier*/
if ( i % j == 0 ) {
p1_est_premier = 0;
break;
}
/*test si p2 est premier*/
if ( (i + 2) % j == 0 ) {
p2_est_premier = 0;
break;
}
}
if ( p1_est_premier == 1 && p2_est_premier == 1 ) return;
}

[inviteb7bc207b]

Spi100,

Tu illustres bien ce que je dis: ton soucis n'est pas de savoir si le programme P que tu viens d'écrire va s'arrêter ou non. Ce que tu cherches c'est H qui te permettrait de "prouver" P. Admets que c'est plutot académique comme question (à quoi on a répondu d'ailleurs).

[spi100]

Spi100,

Tu illustres bien ce que je dis: ton soucis n'est pas de savoir si le programme P que tu viens d'écrire va s'arrêter ou non. Ce que tu cherches c'est H qui te permettrait de "prouver" P. Admets que c'est plutot académique comme question (à quoi on a répondu d'ailleurs).

Non, la conjecture des nombres jumeaux n'a pas de réponse à ce jour.
Non, je ne cherche pas H, je sais qu'il n'existe pas.
Et oui le sujet de ce fil de discussion est effectivement académique, donc difficile de ne pas utiliser d'illustrations académiques.

[invite73192618]

Sinon pour le programmeur son soucis dans la vraie vie n'est pas H mais plutot pourquoi P s'est-il arrêté intempestivement avant de donner un résultat

Si tu pouvais faire H, alors tu pourrais tester automatiquement quelles variations de P donnent un résultat... et tu dis que ce ne serait pas important?

[inviteb7bc207b]

En fait la question est mal posé. Dans le mot ordinateur, il y a calculabilité et beaucoup plus.
On aurait pu imaginer d'autres titres à cette discussion.

1/ Le réel est il calculable ?
2/ Le réel est il compréhensible ?
3/ Le réel est il simulable ?
Ces 3 questions ne sont pas équivalentes.

1/ La calculabilité est clairement définie, les limites en sont connues et l'on sait comment aller au-delà : les O-machines de Turing par exemple. Ca n'a rien de très étonnant, ça consiste juste à dire que si tu injectes des connaissances non-algorithmiques dans un algorithme, tu peux aller au delà du simple programme. Il peut par exemple s'agir d'initier un programme avec un nombre complètement aléatoire, générer à partir d'un phénomène physique réputé aléatoire.

2/ La compréhension ne se ramène pas à un simple problème d'arithmétique ou de logique, il s'agit plus d'essayer de sémantiser les phénomènes sans forcemment se restreindre à un seul système logique.

3/Le réel est-il simulable, peut - être et même si l'on admet qu'il n'est pas calculable. C'est le cas si tu considères que le continu a un sens physique et que le hasard existe aussi i.e. la grande majorité des théories physiques.

C'est un peu vite dit à mon avis.
Sur le premier point: penses-tu que le réel n'est pas calculable uniquement à cause de "la machine de Turing" ?
Par exemple les lois de l'attraction étant connues je peux calculer le mouvement de 2 corps mais s'il y a 3 corps en jeu jusqu'où je peux prédire leur mouvements ? Et pourquoi ?

Je pense aussi que le réel n'est pas calculable mais pas à cause du problème de la machine de Turing.

[spi100]

C'est un peu vite dit à mon avis.

oui surement, on evacut pas une question pareille en deux lignes.

Sur le premier point: penses-tu que le réel n'est pas calculable uniquement à cause de "la machine de Turing" ?

Vu que la calculabilité est une façon de définir la calculabilité. Oui, mais c'est presque un pléonasme.

Par exemple les lois de l'attraction étant connues je peux calculer le mouvement de 2 corps mais s'il y a 3 corps en jeu jusqu'où je peux prédire leur mouvements ? Et pourquoi ?

Oui, effectivement là tu évoques encore une autre facette : la prédictibilité. Un système calculable n'est pas nécessairement predictible, les systèmes chaotiques tel que le problème à 3 corps en sont un exemple. Un exemple plus didactique est le jeu de la vie de Conway qui est parfaitement calculable, la preuve tu peux le faire tourner sur ton ordinateur, néanmoins il est quasiment impossible de deviner son comportement à long terme.

Je pense aussi que le réel n'est pas calculable mais pas à cause du problème de la machine de Turing.

Non, là tu confonds prédictibilité et calculabilité (voir ma remarque ci-dessus).

[inviteb7bc207b]

Là je crois qu'une défintion de "calculabilité" s'impose.

Qu'entends tu par calculabilité ?

Par exemple est-ce qu'on considère que pi est calculable ?

[spi100]

Là je crois qu'une défintion de "calculabilité" s'impose.

Qu'entends tu par calculabilité ?

La calculabilité est définie par la thèse de Church-Turing. On la trouve sous différentes formes.
Une forme savante -à la Church- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des fonctions récursives.
Une autre façon -à la Turing- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des machines de Turing.

Par exemple est-ce qu'on considère que pi est calculable ?

Un nombre est calculable ssi il existe un algorithme (i.e. une machine de Turing ou une fonction récursive) permettant d'approcher ce nombre avec une précision arbitrairement petite.

Dans le cadre de cette définition on montre bien que pi est calculable. Par contre il existe une infinité de nombres non calculables. Je l'ai déjà dit plus haut dans ce fil ou peut être dans un autre, mais la quasi-totalité des réels ne sont pas calculables.
Des exemples de nombres définissables mais non calculables ont été donnés par Turing et Chaitin.

Pour le nombre de Turing, tu commences par énumérer tous les programmes possibles. Tu regardes si le programme N s'arrête ou boucle, si arret alors tu mets le bit N à 0 sinon à 1. Comme le halting programme n'existe pas ce nombre est définissable mais pas calculable.

Pour le nombre de Chaitin, c'est la probabilité d'arret d'un programme
avec p(n) le nombre de programmes de taille n qui s'arrêtent.
Comme p(n) n'est pas calculable, nous avons défini un nombre qui n'est pas calculable.

[inviteb7bc207b]

spi100,

La "calculabilité" selon Turing n'est pas ce que j'appelle "la calculabilté du réel". En effet le résultat d'une machine de Turing est discret alors que le réel est continu.

Tu prends le jeu de la vie comme exemple de système chaotique. Mais la différence avec le problème des trois corps c'est que si tu as l'état initial du jeu de la vie tu peux répéter exactement son évolution. Alors que dans le cas du problème des 3 corps ce n'est pas évident que tu obtienne toujours le même résultat au bout de N pas de calcul.

Pour PI tu as juste donné la calculabilité de toute approximation de PI mais pas de PI lui même.


Tout ça pour dire qu'à mon avis on peut aussi s'intéresser à la question "les ordinateurs peuvent - ils résoudre tous les problèmes ?" par rapport à la nature continu du "réel", du hasard (intrinsèque ou manque de connaissance ?) etc.

[spi100]

Tu prends le jeu de la vie comme exemple de système chaotique. Mais la différence avec le problème des trois corps c'est que si tu as l'état initial du jeu de la vie tu peux répéter exactement son évolution. Alors que dans le cas du problème des 3 corps ce n'est pas évident que tu obtienne toujours le même résultat au bout de N pas de calcul.

Si tu simules un problème à 3 corps sur un ordinateur, tu ne pourras pas prévoir le comportement le premier coup, mais si tu rejoues la simulation tu trouveras à chaque coup le même résultat.
Ce n'est pas un problème de chaos mais juste le fait que sur un ordinateur classique tu as un limitation intrinsèque de précision (32 bits ou 64 bits). Donc évidemment d'une execution à l'autre, tu te trouveras tjs dans les mêmes conditions.

Pour PI tu as juste donné la calculabilité de toute approximation de PI mais pas de PI lui même.

La définition que je t'ai donné n'est relative à aucune méthode d'approximations. C'est juste la possibilité de produire ce nombre à partir d'un algorithme. Il faut bien séparer d'un coté la possibilité de définir un nombre et de l'autre la possibilité de la calculer avec un algo. La définissabilité n'implique pas la calculabilité de PI.
Si tu veux une définition de pi, c'est le rapport du périmètre sur le diamètre d'un cercle quelconque, mais ça ne te permet pas de le calculer.

Tout ça pour dire qu'à mon avis on peut aussi s'intéresser à la question "les ordinateurs peuvent - ils résoudre tous les problèmes ?" par rapport à la nature continu du "réel", du hasard (intrinsèque ou manque de connaissance ?) etc.

C'est un peu flou, est - ce que tu peux préciser ?

[invite06fcc10b]

La calculabilité est définie par la thèse de Church-Turing. On la trouve sous différentes formes.
Une forme savante -à la Church- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des fonctions récursives.
Une autre façon -à la Turing- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des machines de Turing.

Un nombre est calculable ssi il existe un algorithme (i.e. une machine de Turing ou une fonction récursive) permettant d'approcher ce nombre avec une précision arbitrairement petite.

Dans le cadre de cette définition on montre bien que pi est calculable. Par contre il existe une infinité de nombres non calculables. Je l'ai déjà dit plus haut dans ce fil ou peut être dans un autre, mais la quasi-totalité des réels ne sont pas calculables.
Des exemples de nombres définissables mais non calculables ont été donnés par Turing et Chaitin.

Il y a un problème. On ne peut pas dire que Pi est calculable sous prétexte qu'on peut "l'approcher". Ou on trouve Pi ou on ne le trouve pas. Je dirais donc personnellement que Pi n'est pas calculable, seule une valeur approchée de Pi l'est, ce qui n'est pas pareil !
L'ambiguité, c'est qu'il existe un algorithme pour calculer Pi. Mais c'est une croyance erronée, il existe un algorithme pour calculer une valeur approchée de Pi, pas pour calculer Pi. On peut même le prouver en disant que quelle que soit l'étape de calcul à laquelle on s'arrête, le nombre trouvé n'est pas Pi !

Je préférerais donc la définition suivante :
"Une autre façon -à la Turing- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des machines de Turing qui fournissent un résultat au bout d'un temps fini."

[spi100]

Il y a un problème. On ne peut pas dire que Pi est calculable sous prétexte qu'on peut "l'approcher". Ou on trouve Pi ou on ne le trouve pas. Je dirais donc personnellement que Pi n'est pas calculable, seule une valeur approchée de Pi l'est, ce qui n'est pas pareil !

On peut l'approcher avec "une précision arbitrairement petite", tout est dans le "arbitrairement petite". En d'autres termes ça dit qu'en un temps fini tu attendras la précision que tu t'es fixée.

Ta définition revient presque au même sauf que tu perds la notion de précision en énoncant les choses de cette façon.

L'ambiguité, c'est qu'il existe un algorithme pour calculer Pi. Mais c'est une croyance erronée, il existe un algorithme pour calculer une valeur approchée de Pi, pas pour calculer Pi. On peut même le prouver en disant que quelle que soit l'étape de calcul à laquelle on s'arrête, le nombre trouvé n'est pas Pi !

Il existe des algo permettant de calculer PI avec une précision arbitrairement petite. Si effectivement tu oublies les termes "précision arbitraire", c'est faux, si tu les précises c'est juste.

Je préférerais donc la définition suivante :
"Une autre façon -à la Turing- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des machines de Turing qui fournissent un résultat au bout d'un temps fini."

Tu rédéfinis la calculabilité à ta sauce, elle n'est pas compatible avec la définition de Turing car elle ne permet pas d'identifer l'ensemble des fonctions calculables avec celui des fonctions récursives. Tu exclus tous les algorithmes qui partent en boucle infini, ils sont essentiels à la théorie de la calculabilité.

[kaya31]

Je préférerais donc la définition suivante :
"Une autre façon -à la Turing- est de dire que l'ensemble des fonctions calculables est exactement l'ensemble des machines de Turing qui fournissent un résultat au bout d'un temps fini."

Dans ce cas, tu peux éliminer tous les irrationnels de la calculabilité...
En effet, tu ne pourras jamais écrire une suite infinie de décimales en un temps fini...

[spi100]

Dans la même veine, tu peux aussi exclure toutes les fractions de nombres premiers entre eux, genre 10/3 = 3.3333....

[inviteb7bc207b]

Je peux comprendre que selon la définition similaire aux limites des suites PI est calculable. Mais dans ce cas il doit exister un grand nombre de nombres réels qui ne soient pas calculable selon cette définition non ?

[invite73192618]

Tout à fait: si tu prends un nombre au hasard ("vrai"), alors il a toute les chances d'être non calculable.

[inviteb7bc207b]

C'est bien! Voilà donc des "problèmes" non solvables par ordinateur et qui n'ont rien à voir avec la condition d'arrêt de Turing. On avance.

[invite06fcc10b]

Dans la même veine, tu peux aussi exclure toutes les fractions de nombres premiers entre eux, genre 10/3 = 3.3333....

Effectivement.
Mais il n'échappera à personne que :
1) Aucun être humain n'est capable d'accéder à la valeur exacte d'un nombre irrationnel. Si nous nous n'en sommes pas capables, c'est qu'on a franchi une certaine barrière, non ?
2) Dans les calculs sur les fractions, rien ne nous empêche (nous c'est l'être humain ou l'ordinateur) de représenter le nombre sous la forme fractionnaire, c'est à dire numérateur et dénominateur, et ça suffit largement.
Bref, c'est calculable, complètement, et exactement ... tant qu'on n'essaie pas d'accéder à toutes les décimales.

ps : comme je l'ai déjà suggéré par ailleurs, c'est pareil pour les réels. Tant qu'on peut garder le réel sous sa forme symbolique (par exemple "pi"), cela n'est pas gênant pour le "calcul", cela reste calculable ! Maintenant, si on souhaite connaître les décimales, là non ce n'est pas calculable.

[spi100]

Effectivement.
Mais il n'échappera à personne que :
1) Aucun être humain n'est capable d'accéder à la valeur exacte d'un nombre irrationnel. Si nous nous n'en sommes pas capables, c'est qu'on a franchi une certaine barrière, non ?
2) Dans les calculs sur les fractions, rien ne nous empêche (nous c'est l'être humain ou l'ordinateur) de représenter le nombre sous la forme fractionnaire, c'est à dire numérateur et dénominateur, et ça suffit largement.
Bref, c'est calculable, complètement, et exactement ... tant qu'on n'essaie pas d'accéder à toutes les décimales.

ps : comme je l'ai déjà suggéré par ailleurs, c'est pareil pour les réels. Tant qu'on peut garder le réel sous sa forme symbolique (par exemple "pi"), cela n'est pas gênant pour le "calcul", cela reste calculable ! Maintenant, si on souhaite connaître les décimales, là non ce n'est pas calculable.

Effectivement plutot que de travailler sur les fractions en les exprimant sous formes décimals, je peux travailler sur des couples de nombres.
10/3 est le couple (10,3)
Je considère un ensemble de couples sur lequel je vais définir un loi d'addition : (a,b) + (c,d) = (ad+bc, bd)
une multiplication (a,b).(c,d) = (ac, db)
une relation d'équivalence (ka, kb) = (a,b).
Manifestement ça ne te choque pas et tu trouves cette démarche parfaitement naturelle.
Pourtant tu manipules une structure abstraite qui te permet de réaliser des déductions sur les nbres rationnels, sans jamais avoir à les exprimer sous forme décimal.

De même tu peux définir les nombres irationnels comme étant les 0 d'un polynome. Tu feras des déductions sur les nombres irrationnels en manipulant l'algèbre des polynomes, sans jamais avoir à les exprimer.

De même tu feras des déductions sur les nombres transcendants, en manipulant les relations de récursions qui les définissent.

Expliques-moi en quoi ces 3 situations ne sont pas similaires ?

[bardamu]

Une petite avancée intéressante : http://www.inria.fr/actualites/2005/...uleurs.fr.html

Extrait :

Coq, l'outil d'aide à la preuve
Ces logiciels, appelés aussi assistants de preuve, permettent de vérifier entièrement des démonstrations (ou preuves) mathématiques, pourvu que celles-ci soient rédigées dans un langage informatique dédié. La vérification repose entièrement sur des règles syntaxiques maîtrisées et issues de la logique mathématique ; on parle alors de preuve formelle. Cette automatisation fiabilise le processus de validation et exclu, par exemple, les «erreurs d'inattention ».

Plus précisément, en Coq, les démonstrations mathématiques sont décrites à l'aide d'une suite de commandes appelées « tactiques ». Coq traduit ces commandes en une preuve formelle. L'environnement d'exécution de Coq vérifie alors que l'ensemble de cette preuve obéit bien aux lois de la déduction mathématique.

Une originalité de Coq est que son langage mathématique inclut dès l'origine des programmes informatiques. Les fonctions mathématiques sont donc décrites par des algorithmes exécutables. Ainsi, la logique de Coq permet de combiner les résultats calculatoires donnés par l ‘exécution des programmes et la déduction mathématique conventionnelle. C'est cette caractéristique qui met à la portée de Coq des résultats comme le théorème des quatre couleurs dont la démonstration ne peut être décrite par un texte mathématique au sens traditionnel.

Au final, c'est donc la première fois que l'ensemble de la démonstration du théorème des quatre couleurs est exprimée dans un seul et même langage évitant le mélange des disciplines (mi-mathématique ou mi-informatique), source potentielle d'erreurs.

[invite06fcc10b]

Effectivement plutot que de travailler sur les fractions en les exprimant sous formes décimals, je peux travailler sur des couples de nombres.
10/3 est le couple (10,3)
Je considère un ensemble de couples sur lequel je vais définir un loi d'addition : (a,b) + (c,d) = (ad+bc, bd)
une multiplication (a,b).(c,d) = (ac, db)
une relation d'équivalence (ka, kb) = (a,b).
Manifestement ça ne te choque pas et tu trouves cette démarche parfaitement naturelle.
Pourtant tu manipules une structure abstraite qui te permet de réaliser des déductions sur les nbres rationnels, sans jamais avoir à les exprimer sous forme décimal.

De même tu peux définir les nombres irationnels comme étant les 0 d'un polynome. Tu feras des déductions sur les nombres irrationnels en manipulant l'algèbre des polynomes, sans jamais avoir à les exprimer.

De même tu feras des déductions sur les nombres transcendants, en manipulant les relations de récursions qui les définissent.

Expliques-moi en quoi ces 3 situations ne sont pas similaires ?

Tout est une question de procédure de calcul. Tant que la procédure de calcul est réalisable en un nombre fini d'étapes, avec un nombre fini d'états, c'est calculable.
Ainsi, tant qu'on reste en symbolique ou qu'on manipule des couples de nombres finis, manifestement, on respecte le nombre finis d'étapes et d'états de la procédure de calcul. Si en revanche dans la procédure de calcul on cherche à calculer toutes les décimales
d'un nombre qui en comporte un nombre infini, on viole un ou les 2 principes précédents.