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

[spi100]

Bonjour,
J'ouvre cette discussion à la suite de "L'intelligence artificielle peut-elle se révéler néfaste ?". Le fil avait pas mal dévié de la question initiale et nous en étions arrivés à nous demander s'il existait des nombres qui ne soient pas calculables par une machine de turing, ou même des problèmes qui ne soient pas solvables par des programmes ?

[erik]

La réponse à la question existe t il des problèmes qui ne soient pas solvables par des programmes est oui.

Un exemple : supposons que l'on ait écrit un programme P qui doit résoudre un problème donné, une question naturelle est : est ce que mon programme va donner la (une) solution en un temps fini ou est ce qu'il va se mettre à tourner sans jamais s'arreter (et donc ne jamais donner de solution)?
En bon informaticien on se dit qu'il suffit d'écrire un programme V qui aura comme fonction d'examiner un autre programme qu'on lui donne en entrée et qui répondra soit : oui le programme P que j'examine finira par s'arreter, soit non votre programme P tournera sans arret.

Et bien en fait ce n'est pas une bonne idée, on a montré qu'il est impossible d'écrire le programme V : Il n'existe pas de programme capable de determiner si un autre programme va ou non s'arreter.

[spi100]

Je propose donc la première réponse.

Turing a écrit son article fondateur sur les machines de turing pour formaliser la notion d'algorithme. Il ramène un traitement algoritmique a l'execution d'un automate composé d'un ruban infini et d'une tête de lecture qui peut écrire et lire sur le ruban. Il énonce alors sa thèse "Tout algorithme peut être formulé sous la forme d'une machine de Turing".
Cette énoncé est souvent considéré à tort, et est interprété comme si "Les machines de Turing pouvaient tout résoudre". Je cite par exemple Argyre dans le fil "L'intelligence artificielle est - elle néfaste".

et il arrive un peu plus loin à la conclusion qu'une Machine de Turing ne peut donc prédire un résultat, alors qu'expérimentalement un physicien pourrait le faire.

C'est faux ! Dans le même article où Turing définit sa fameuse machine, il montre que les machines de Turing ne peuvent pas résoudre n'importe quel problème.
Pour sa démonstration, il considère le problème de l'arrêt d'une machine de Turing : Est - il possible de définir une machine de Turing capable de décider si une autre machine de Turing quelconque va s'arrêter ou non. En des termes plus modernes : est - il possible d'écrire un programme capable de déterminer si un programme quelconque s'arrête ou non ?
En procédant par un raisonnement par l'absurde il démontre que non ! J'avais fait une démo simplifiée là http://forums.futura-sciences.com/post254762-20.html .

Turing conclut alors que si la thèse de Church-Turing est juste alors il existe des problèmes qui ne sont pas solvables par des algorithmes.

On peut même montré qu'il existe des nombres qui ne sont pas calculables par un algorithme. Chaitin en a exhibé un : http://mathworld.wolfram.com/ChaitinsConstant.html .
La démonstration de la non - calculabilité de ce nombre est très simple : pour le connaitre il faut connaitre la probabilité qu'un programme de longueur N s'arrête, il faut donc un algorithme capable de statuer si un programme quelconque s'arrête ou non. Or ce programme n'existe, donc le nombre de Chaitin n'est pas calculable. Les matheux disent 'Que le nombre de Chaitin est définissable mais pas calculable'. Attention, ça n'empêche pas d'en faire une estimation en utilisant des moyens empiriques (voir la fin de la page http://mathworld.wolfram.com/ChaitinsConstant.html).

Donc effectivement pour répondre à Argyre : Voici un exemple où des numériciens (pas des physiciens) peuvent prédire un résultat alors qu'une machine de Turing en est incapable.

[spi100]

Croisement avec Erik qui m'a damé le pion

[A voir en vidéo sur Futura]

[yat]

En des termes plus modernes : est - il possible d'écrire un programme capable de déterminer si un programme quelconque s'arrête ou non ?
En procédant par un raisonnement par l'absurde il démontre que non ! J'avais fait une démo simplifiée là http://forums.futura-sciences.com/post254762-20.html .

Turing conclut alors que si la thèse de Church-Turing est juste alors il existe des problèmes qui ne sont pas solvables par des algorithmes.

Il y a quelque chose qui m'échappe un peu dans ce fait. Est-ce que cette impossibilité est liée au caractère infini de la "bande" de la machine de turing ?
Dans le cas contraire je ne comprends pas le truc. Et en l'occurence, pour un programme qui tourne sur un pc (ou, donc, tout est fini), il me semble absolument évident qu'il est possible de faire un algorithme qui dit si un algorithme donné va s'arréter ou non sur une machine A (mais sur une machine B beaucoup plus puissante que A).

...c'est dire combien je dois être à coté de la plaque

Pour la démonstration simplifiée que tu donnes dans l'autre fil, il y a aussi un truc qui m'échappe. Pour commencer, pourquoi dans la boucle, on appelle halt(p,p) plutôt que halt(p) ? Je ne comprends pas ce qu'est sensée renvoyer l'hypothétique fonction halt() quand on lui envoie deux paramètres.

Ensuite, pour ce qui est de la démo en elle-même, je comprends pas tout non plus : si s est la chaine correspondant à boucle_si_halt, contient-elle le paramètre qu'on lui envoie ? Parce qu'au dela de l'algorithme en lui-même, c'est (surtout dans le cas présent) principalement la valeur du paramètre envoyé qui va déterminer si l'algorithme s'arrete ou pas. Or s ne peut pas contenir son algorithme et elle-même ...???

[spi100]

Il y a quelque chose qui m'échappe un peu dans ce fait. Est-ce que cette impossibilité est liée au caractère infini de la "bande" de la machine de turing ?
Dans le cas contraire je ne comprends pas le truc. Et en l'occurence, pour un programme qui tourne sur un pc (ou, donc, tout est fini), il me semble absolument évident qu'il est possible de faire un algorithme qui dit si un algorithme donné va s'arréter ou non sur une machine A (mais sur une machine B beaucoup plus puissante que A).

...c'est dire combien je dois être à coté de la plaque

C'est tout à ton honneur car ce n'est absolument pas intuitif. Non ce n'est pas lié au caractère infini de la bande.

Pour la démonstration simplifiée que tu donnes dans l'autre fil, il y a aussi un truc qui m'échappe. Pour commencer, pourquoi dans la boucle, on appelle halt(p,p) plutôt que halt(p) ? Je ne comprends pas ce qu'est sensée renvoyer l'hypothétique fonction halt() quand on lui envoie deux paramètres.

C'est une erreur de ma part, il faut bien lire halt(p) et pas halt(p,p).

Ensuite, pour ce qui est de la démo en elle-même, je comprends pas tout non plus : si s est la chaine correspondant à boucle_si_halt, contient-elle le paramètre qu'on lui envoie ? Parce qu'au dela de l'algorithme en lui-même, c'est (surtout dans le cas présent) principalement la valeur du paramètre envoyé qui va déterminer si l'algorithme s'arrete ou pas. Or s ne peut pas contenir son algorithme et elle-même ...???

S est la succession de caractères correspondant au programme boucle_si_halt : rien ne t'empêche d'appliquer boucle_si_halt sur S.

La contradiction vient du fait que tu appliques le programme à lui même.
C'est du même type que la paradoxe des ensembles qui ne s'appartiennent pas d'Husserl ou du menteur de Parménide :tu fabriques un énoncé contradictoire en prenant un élément qui se définit en se référant à lui-même.

[yat]

S est la succession de caractères correspondant au programme boucle_si_halt : rien ne t'empêche d'appliquer boucle_si_halt sur S.

C'est bien là que je pige pas : un programme, il lui faut des paramètres pour tourner. Quand je passe à la fonction halt() un programme pipo(entier a, entier b) pour savoir s'il va s'arréter, il faut bien que je lui donne aussi les paramètres a et b que je lui envoie... Et donc c'est donc exactement la même chose avec boucle_si_halt : ses paramètres, ce sont un programme et les paramètres qu'on lui passe.

Si la fonction halt() pouvait exister, on pourrait donc sans problème appeler boucle_halt(fonction1(a,b,c)), et du coup appeler boucle_halt(boucle_halt(foncti on1(a,b,c))). Mais pour moi, appeler boucle_halt sur elle-même ne veut tout simplement rien dire. Mais je ne vois absolument pas en quoi cela permet de démontrer la non-existence de cette fonction.

De la même manière, on ne peut pas construire un fichier zip qui se contienne lui-même, mais on peut faire un zip avec n'importe quel fichier, et faire un zip de ce zip, et ainsi de suite. Ca ne change absolument rien au fait qu'il existe un programme winzip qui permet de mettre n'importe quel type de fichier dans un zip... ou est la différence ?

Peut-être que ça sera plus facile de me coller le nez sur mon erreur si je prends le problème dans l'autre sens : Si une machine de turing a un nombre d'états finis, il suffit de simuler son execution pas à pas en regardant à chaque étape l'état de la machine. Si on retrouve à un moment donné un état déjà trouvé pendant l'exécution du programme, le reste se déroulera exactement de la même manière et le programme ne s'arrètera jamais. Si par contre on sort du programme, on a aussi la réponse. Comme il n'existe pas un nombre infini d'états possibles, on saura si le programme se termine, et en un temps fini. Argh... me voilà en train de démontrer des trucs faux ... bon, il y a nécessairement un truc énorme dans ce que je viens de dire, mais j'arrive pas à voir quoi...

[invite06fcc10b]

C'est faux ! Dans le même article où Turing définit sa fameuse machine, il montre que les machines de Turing ne peuvent pas résoudre n'importe quel problème.

Que de prose pour arriver à une conclusion que Gödel a démontré depuis longtemps. Il y a manifestement un problème de compréhension entre nous, car je suis tout à fait d'accord avec toi sur ce point !
Il est mille fois prouvé que les ordinateurs ne peuvent résoudre tous les problèmes. Là n'est pas la bonne question et je vais donc sortir de ce fil de discussion et en proposer un autre avec la bonne question : existe t-il des problèmes comportant une solution mathématique ou physique qui ne peuvent être résolus de façon algorithmique ? Dit autrement : les ordinateurs peuvent-ils résoudre tous les problèmes SOLVABLES !

[spi100]

existe t-il des problèmes comportant une solution mathématique ou physique qui ne peuvent être résolus de façon algorithmique ? Dit autrement : les ordinateurs peuvent-ils résoudre tous les problèmes SOLVABLES !

Le calcul du nombre de Chaitin ne te suffit pas comme exemple ?

[invite06fcc10b]

Le calcul du nombre de Chaitin ne te suffit pas comme exemple ?

Certainement pas, car personne ne peut prétendre pouvoir calculer ce nombre qui comporte un nombre infini de décimales.
C'est un problème que personne ne peut résoudre, ni humain ni machine, il est donc hors-sujet.

[spi100]

Certainement pas, car personne ne peut prétendre pouvoir calculer ce nombre qui comporte un nombre infini de décimales.
C'est un problème que personne ne peut résoudre, ni humain ni machine, il est donc hors-sujet.

Pi est il calculable pour toi ? Voilà aussi un nombre qui comporte un nombre infini de décimales et qui est pourtant calculable au sens de la calculabilité.

[invite06fcc10b]

Pi est il calculable pour toi ? Voilà aussi un nombre qui comporte un nombre infini de décimales et qui est pourtant calculable au sens de la calculabilité.

Disons qu'il est calculable en théorie si on disposait d'un temps infini, mais il n'est pas calculable expérimentalement.
D'où le terme solvable (euh... plutôt soluble au fait, non ?) qui rajoute un côté pragmatique à la notion de calculabilité.

[spi100]

Disons qu'il est calculable en théorie si on disposait d'un temps infini, mais il n'est pas calculable expérimentalement.
D'où le terme solvable (euh... plutôt soluble au fait, non ?) qui rajoute un côté pragmatique à la notion de calculabilité.

Alors si tu préfères je pose le problème de cette façon :

Problème solvable : "Peux t'on calculer avec un algorithme, pi avec une précision arbitrairement petite ?"
Oui.

"Peut - on calculer avec un algorithme le nombre de Chaitin, avec une précision arbitrairement petite ?"
Non

Tu remarqueras que le problème posé n'est pas d'écrire dans sa totalité ou (le nbre de Chaitin).

[spi100]

Yat,
C'est peu être le mécanisme de la démonstration qui te gêne. Regarde celle là http://forums.futura-sciences.com/post256046-22.html ce n'est pas sur le même sujet mais elle utilise exactement le même mécanisme que celle de Turing.

[yat]

Yat,
C'est peu être le mécanisme de la démonstration qui te gêne. Regarde celle là http://forums.futura-sciences.com/post256046-22.html ce n'est pas sur le même sujet mais elle utilise exactement le même mécanisme que celle de Turing.

Oui, je comprends bien l'exemple donné, il est effectivement très simple. Mais pour le problème de la machine de turing, ça ne se passe pas de la même manière : c'est le fait même d'appliquer le programme boucle_halt() sur lui-même qui n'a pas de sens, pour moi. En effet, appeler boucle_halt() sans argument n'a aucun sens. Avant de se poser la moindre question sur son comportement, il faut d'abord préciser ce qu'on lui donne en paramètre.

Enfin, ça, ça ne fait qu'embrouiller encore un peu plus les choses dans ma tête. Le fait est que je ne vois toujours pas en quoi ça prouve que halt() ne peut pas exister : J'ai l'impression qu'on peut faire exactement le même raisonnement pour une fonction un peu différente :

Il s'agit de montrer qu'il n'existe pas de programme retour() capable de déterminer si un programme P qui s'arrete en renvoyant une valeur booléenne renvoie vrai.

On suppose que retour(p) existe, avec p la chaine de caractères représentant le programme P . Cette fonction retourne true si P renvoie true ou false sinon.

On peut à partir de retour(), ecrire le programme

retour_faux(p)
{
if ( retour(p,p) == false )
return true
else
return false
}

retour_faux est représenté par une chaîne de caractères que l'on nomme s. Rien n'empêche d'appliquer retour_faux sur s. On a alors :

si retour_faux(s) renvoie true alors retour(s) = true et retour_faux(s) renvoie false.
si retour_faux(s) renvoie false alors retour(s) = false et retour_faux(s) renvoie true.

On a bien ici un énoncé tel que A implique non A, avec
A = "retour_faux(s) renvoie true".

La conclusion que l'on en tire ici, est que retour_faux() n'existe pas et ainsi retour() n'existe pas. De même dans le cas général 'A implique non A" permet de conclure que A n'existe pas.

Alors que retour(), y a pas de problème, elle existe. En quoi cette démonstration diffère de celle sur la fonction qui dit si un programme s'arrète ? Ca m'inquiète, ça... si je peux pas comprendre un truc qui est manifestement aussi évident, je n'ai plus qu'à aller là ou je dois être :

[invite06fcc10b]

Peut - on calculer avec un algorithme le nombre de Chaitin, avec une précision arbitrairement petite ?
Non

Peu importe si oui ou non on peut ou pas calculer quelque chose avec un algorithme, le problème est de trouver quelque chose non calculable par un algorithme et calculable par un autre moyen (expérimental, pas théorique), sans être obligé de faire référence à un infini temporel, spatial, ou une continuité de la matière espace-temps.

[spi100]

Pourtant c'est bien le coeur du problème et je ne vois pas en quoi la définition de la calcubilité d'un nombre fait référence a "un infini temporel" ou "une contuinité de la matière espace temps" ? Mais si tu veux un autre exemple :

- donner une séquence de nombres complètement aléatoire : un algorithme ne le peut pas, mais tu peux utiliser un phénomène physique comme une désexitation radioactive.

[spi100]

retour_faux(p)
{
if ( retour(p,p) == false )
return true
else
return false
}

retour_faux est représenté par une chaîne de caractères que l'on nomme s. Rien n'empêche d'appliquer retour_faux sur s. On a alors :

si retour_faux(s) renvoie true alors retour(s) = true et retour_faux(s) renvoie false.
si retour_faux(s) renvoie false alors retour(s) = false et retour_faux(s) renvoie true.

Non ton exemple ne marche pas car on ne sait pas ce que doit faire la fonction retour(), elle n'est pas spécifiée.
Dans le cas du 'halting problem', la fonction halt est parfaitement spécifiée mais n'est pas implémentable.
Est - ce que tu es plutot programmeur ou matheux ? Je peux te proposer d'étayer un peu plus mais je ne sais pas si tu préfères que je me lance dans une démo plus abstraite ou dans un exemple plus concret.