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

[kaya31]

Bonjour,

En ce qui concerne le problème des polynomes sans racines entières, il me semble qu'il y a une différence entre existence et identification.
Le théorème de Robinson-Matijacevic montre l'existence et au dela, la non possibilité d'identification. C'est a dire que pour un polynome donné, un algorithme ne pourra determiner qu'il n'a pas de racine entiere. En gros c'est le probleme de l'identification pour un polynome donné qui n'est pas solvable.
Le contenu du théorème montre qu'il existe un problème non solvable.
Très bien. Mais en quoi cela signifie t'il qu'une machine de turing ne pourrait pas démontrer ce théorème ??? Ceka démontre simplement qu'une machine de turing ne pourra pas identifier un de ces polynomes puisque c'est un problème non solvable.
Enfin bref, a moins d'avoir rater quelque chose, je vois pas où est la contradiction.
-----

[invite06fcc10b]

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.

Non, je ne me trompe pas. J'ai lu la page à laquelle tu fais référence, il est dit :
"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."

En fait, ils montrent cette propriété en sortant de l'ensemble des entiers naturels et de ses axiomes, mais ils utilisent bien d'autres axiomes dans le cadre de l'ensemble des nombres réels.
Il s'agit donc bien d'un raisonnement (peu importe le cadre théorique), qui peut être reproduit par un algorithme.
Le fait de se placer dans une théorie qui accepte les nombres réels, alors qu'aucun algorithme ne peut accéder à la valeur exacte de celui-ci n'est pas important tant qu'il n'y a pas besoin d'accéder à cette valeur pour les besoins de la démonstration. Nous-mêmes avons ces mêmes limites. Par exemple, le nombre PI ne peut être calculé par aucun algorithme. Ce qui peut être calculé, c'est une partie du nombre PI. Cela ne nous empêche pas d'utiliser le nombre PI de manière formelle et de le traiter comme une variable dans une équation, par exemple 2*PI*R si on fait référence au périmètre d'un cercle dans une démonstration. Mais ce traitement formel reste bien entendu algorithmique.

Basiquement, il faut bien comprendre les travaux de Church et Turing. En gros, dès qu'il y a un procédé, donc une séquence de propositions, qui explicite un raisonnement mathématique quelconque, alors on peut décomposer ce procédé en propositions élémentaires pour former un algorithme.
Le seul problème pourrait venir d'un besoin d'accéder à une valeur "infinie" si cela a un sens. Mais notre cerveau a les mêmes limites car nous n'avons pas de mémoire infinie, ni de ressources temporelles infinies.
A la rigueur, si l'espace-temps est continu (ça reste à prouver), on doit pouvoir calculer des choses qu'un algorithme sur le papier ne peut calculer (hypercomputing). Mais il s'agit de moyens technologiques, qui s'ajouteraient aux capacités humaines comme à celles des machines. Tout calcul théorique réalisé exclusivement sur le papier reste de nature algorithmique.

[spi100]

Très bien. Mais en quoi cela signifie t'il qu'une machine de turing ne pourrait pas démontrer ce théorème ??? Ceka démontre simplement qu'une machine de turing ne pourra pas identifier un de ces polynomes puisque c'est un problème non solvable.
Enfin bref, a moins d'avoir rater quelque chose, je vois pas où est la contradiction.

Non, effectivement, ça ne signifie pas qu'une machine de Turing ne peut pas démontrer le théorème.

Ca veut simplement dire que si tu te places dans une structure axiomatique ne permettant que de construire et de manipuler des entités dénombrables (axiomes de Peano), tu ne peux pas prouver que ces polynomes n'admettent pas de racines entière, mais tu ne peux pas prouver le contraire non plus.

Si tu te places dans une axiomatique tenant compte des réels (axiomatique de Fraenkel-Zermello), tu peux prouver que ces polynomes n'admettent pas de racines.

Voilà il n'y effectivement pas de contradiction, l'hypothèse est consistante avec le système de Peano, mais pas réfutable.
Elle devient vrai avec le système de Fraenkel-Zermello qui contient le système de Peano.

Maintenant, et je pense que c'est là que vient la mécompréhension avec Argyre, c'est qu'il faut distinguer le système de raisonnement et les axiomes utilisés.
J'utilise les axiomes de Fraenkel et Zermello, qui contient un certain nombre d'énoncés A1, A2, .... An permettant de construire l'ensemble des réels. J'utilise ensuite pour manipuler ces énoncés des algorithmes. Ce qui me permet de construire des théorèmes sur les réels.
Je ne peux pas utiliser une machine de Turing pour écrire n'importe quel réel ( nombre de Chaitin par exemple), mais je peux très bien utiliser une machine de Turing pour manipuler par sa définition symbolique.

[spi100]

Je suis allé un peu vite pour l'axiomatique de Fraenkel - Zermello, il me semble qu'il faut lui ajouter l'axiome du continu ou l'axiome de choix, si on veut construire les réels.

[pi-r2]

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 ?

Non, car en fait il y a confusion de niveau d'algorithme. La démonstration qu'ils n'admettent pas de racines entières est mathématique, donc algorithmique. Le fait qu'on ne puisse pas le vérifier avec un algorithme primitif (du genre essayer toutes les racines) n'est pas une preuve.

[pi-r2]

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.

Non, Les formules récursives peuvent être écrites et sont grammaticalement correctes. elles ont le droit d'exister.

Petite analogie physique sur la récursivité (en l'occurrence plutôt l'auto-référence):
On dispose d'un relai électro magnétique, c'est à dire d'un interrupteur commandé comme suit:

Commande ---Z
' . . . . . . . . . _ Interrupteur
Entrée ______ ____ Sortie
Quand un courant entre par la commande (et va à la masse) la bobine ouvre l'interrupteur. La sortie est donc 0
Quand il n'y a pas de courant dans la bobine , l'interrupteur est fermé. Dons sortie = entrée

On a donc en terme logique: Si Commande=1 alors sortie= 0 sinon Sortie = Entrée

Que se passe-t-il si j'en fait un auto-référent ? J'ai le droit il suffit de relier Sortie à commande par un fil.
Et je mets entrée = 1
Alors Commande=0 donc sortie = Entrée = 1
Comme commande = sortie, commande=1 donc sortie = 0 donc commande = 0 donc sortie =1

Impossible ? en logique oui, sortie n'a pas de valeur logique 0 ou 1 Sortie est "quelquechose" de nouveau pour la logique.
En physique , non, c'est possible: fais le montage , ça marche en courant continu sur pile.
On obtient un oscillateur, une horloge, un truc qui fait tic tac.

Les autoréférences ne sont ni vraies ni fausses, certes , mais elles existent

PS: avec mon relai, on peut construire ainsi tout un ordinateur ....

[spi100]

Non, car en fait il y a confusion de niveau d'algorithme. La démonstration qu'ils n'admettent pas de racines entières est mathématique, donc algorithmique. Le fait qu'on ne puisse pas le vérifier avec un algorithme primitif (du genre essayer toutes les racines) n'est pas une preuve.

Oui, d'accord avec ce que tu dis il y a bien deux niveaux :
-> Il n'y a pas d'algorithme -utilisant juste la définition des entiers naturels- capables de montrer ce résultat.
-> Il y a des algorithmes manipulant des propositions et des axiomes d'analyses, capables de montrer ce résultat.

[spi100]

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.

La phrase de Pi-R2 n'est pourtant pas si loin de ce que Goedel a démontré. En substance, il a montré que quelque soit le système d'axiome SA que l'on utilise, il est toujours possible de fabriquer un théorème de SA énoncant "Je ne suis pas un théorème de SA".

[invite06fcc10b]

On a donc en terme logique: Si Commande=1 alors sortie= 0 sinon Sortie = Entrée

Que se passe-t-il si j'en fait un auto-référent ? J'ai le droit il suffit de relier Sortie à commande par un fil.
Et je mets entrée = 1
Alors Commande=0 donc sortie = Entrée = 1
Comme commande = sortie, commande=1 donc sortie = 0 donc commande = 0 donc sortie =1

Impossible ? en logique oui, sortie n'a pas de valeur logique 0 ou 1 Sortie est "quelquechose" de nouveau pour la logique.
En physique , non, c'est possible: fais le montage , ça marche en courant continu sur pile.
On obtient un oscillateur, une horloge, un truc qui fait tic tac.

Ta modélisation est complètement erronée, tu confonds l'égalité et l'affectation. Quand on écrit : "si commande=1 alors sortie=0", on AFFECTE la sortie à la valeur 0 à un temps t' différent de t initial, mais ça ne veut pas dire que sortie sera toujours égal à 0. Quand tu dis commande=sortie, ce n'est pas une égalité, c'est encore une fois une affectation à un temps t" différent.
Les matheux ont malheureusement toujours utilisé le même signe "=" pour désigner une comparaison et une affectation. Du coup, ça embrouille tout le monde, sauf les informaticiens bien entendu qui eux utilisent des signes différents.

[pi-r2]

Les = sont évidement des = d'informaticien c'est à dire des affectations.
Alors je ré-écris ma modélisation au propre (je re précise que ça marche en vrai, hein)
Au départ , à t=0 Entrée passe à 1 (on établit un courant) et reste à 1 tout le temps ensuite.
L'interrupteur étant en position fermé, un courant s'établit jusqu'à la masse, en passant par S donc S=1. La bobine est alors parcourue par un courant, produit un champ magnétique qui soulève l'interrupteur. C'est un phénomène physique , donc pas instantané. Au moment où l'interrupteur s'ouvre, le courant s'arrête, l'interrupteur retombe le courant se rétablit...On a un bel oscillateur, ou horloge.
ça c'est le phénomène physique.
Si on essaie d'imaginer une vitesse de propagation infinie et une ouverture instantanée de l'interrupteur, on est amené à écrire: (avec des égal cette fois, par passage illicite à la limite dt=0)
E = 1 , donc S = 1 , Donc C = 1 , Donc S = 0 ... On est passé en maths et c'est contradictoire. Les maths c'est la physique sans le temps dans ce cas. (et c'est contradictoire parce que le passage à la limite est illicite) .
Donc en physique , ou en info (avec des affecté), ça marche, en math ou en logique, ça marche pas.
C'est Plus clair ?
En notation informatique on a:
Entrée = 1
Commande = 0
Sortie =0
while true
if commande = 0 then 'test interrupteur
sortie= entrée 'propagation du signal si fermé
else
sortie= 0
end
commande=sortie 'propagation du signal
print sortie
wend
En math, sans la possibilité d'introduire le temps, on ne peut pas parler d'état de la sortie. La sortie n'est plus 1 ou 0 c'est autre chose (ici une fonction du temps). On a crée du nouveau grâce à l'auto référence.