|
| Profondeur des échecs par Br***au***ch***2 le
[Aller à la fin] |
| Théorie | |
Profondeur des échecs : Combien de parties d'échecs différentes est-il
possible de jouer ?
Dans le contexte de la "Nouvelle Théorie des échecs", que je développe depuis
déjà trois ans, je rencontre quelques intéressants et difficiles problèmes
théoriques. Je souhaite aujourd'hui aborder précisément l'un d'entre eux très
fortement lié au concept de profondeur des échecs. Commençons avec cette
interrogation typique : Combien de parties d'échecs différentes est-il
possible de jouer ?
Avant de donner une crédible (et toutefois extrêmement difficile à démontrer)
première estimation concernant cette question fondamentale, nous avons besoin
de préciser le contexte de base de nos réflexions présentes. Je suis
grandement intéressé par une investigation fondamentale de la profondeur des
échecs. Or la meilleure voie pour aborder cette question est de prendre en
considération les deux outils d'investigation les plus puissants aujourd'hui
à la disposition du théoricien. Je veux dire les mathématiques et
l'informatique .
Ainsi sommes-nous conduits à poser les deux questions :
1°) Existe-t-il une solution mathématique du jeu d'échecs ?
2°) Existe-t-il une solution informatique du jeu d'échecs ?
La réponse à l'une comme à l'autre est non !
Les raisons sont de nature différente, mais avec au cœur une cause similaire
: le jeu d'échecs fait appel, en tant que paramètres internes, à de trop
grands nombres. Pour clarifier l'examen d'une telle situation il est commode
d'appeler "nombre échiquéen" tout nombre ayant une représentation dans le jeu
d'échecs ou alors plus petit qu'un tel nombre.
Ainsi le plus simple pour illustrer la profondeur du jeu d'échecs est-il de
mettre en évidence des nombres échiquéens d'un niveau exceptionnel, en sorte
que ni les mathématiques ni l'informatique ne soient aptes à traiter des
problèmes complexes faisant intervenir de tels paramètres. En vue de
poursuivre dans cette voie il est particulièrement utile de considérer le
TMN (Theoretical Move Number), qui est précisément le nombre de coups
valides à la disposition du joueur ayant le trait.
Maintenant je propose l'étude d'une partie d'échecs concrète, tant il est
vrai qu'il importe aux échecs de conserver une étroite relation entre les
études théoriques et la pratique des échecs. Ainsi, en suivant la partie
Alekhine-Euwe, Championnat du monde 1937 (2ème partie) Défense Slave D17/12 1-0 (41), il n'est pas difficile de calculer le TMN à chaque demi-coup et
d'observer que celui-ci reste en moyenne supérieur à 32 = 2x2x2x2x2 = 2[5] (2 à la puissance 5). Une constatation similaire peut être faite sur toute autre partie.
De plus il est possible de se limiter à des jeux durant >40 coups ou plus. En procédant ainsi nous sommes conduits à envisager le nombre astronomique, donné en tant qu'estimaion inférieure acceptable : E = 2[400] (2 à la puissance 400).
Mon opinion est que ce nombre est un "nombre échiquéen". Plus exactement je formule la
conjecture mathématique : Le nombre de parties d'échecs valides,
compte tenu des règles de la FIDE, est plus grand que : E = 2[400].
En guise de comparaison pensez au nombres suivants :
Parties d'échecs dans les bases de données : moins que 2[20]
Etoiles dans l'univers : approximativement 2[28]
Population mondiale : moins que 2[33]
Nombre de secondes depuis le big bang : moins que 2[59]
Toutes ces informations proviennent du chapitre III de la "Nouvelle Théorie
des Echecs" Copyright "Chess Theory" 2004 :
Profondeur des échecs
Michel Bruneau "Chess Theory" webmestre
|
|
|
1°) Existe-t-il une solution mathématique du jeu d'échecs ? La réponse est oui : le jeu d'échecs est décidable !
C'est d'ailleurs l'unique "théorème" (mon vieux prof de Spéciales aurait sans doute dit que vu la simplicité de la démonstration, ce résultat ne mérite pas mieux que l'appelation "Proposition" ...) intéressant sur le jeu d'échecs.
Mais malheureusement de complexité exponentielle donc, en effet pas de solution pour l'informatique dite classique (par opposition à quantique cf. par ex. http://wwww.qubit.org
La seule connaissance du jeu est donc pratique (heureusement car sans cela, le jeu ne serait peut-être plus aussi populaire) : compréhension humaine du jeu + apport de la puissance de calcul des ordinateurs (essentiellement pour "vérifier" tactiquement des coups).
|
|
|
avec un w de moins c'est mieux qubit
|
|
|
qubit
|
|
|
Liens à lire sur le sujet
http://mathworld.wolfram.com/Chess.html(en anglais)
http://www.cs.berkeley.edu/~flab/echecs/echecs.html (en francais)
|
|
|
vois pas Le lien entre les grands nombres, qui mettent la solution hors de portée de nos moyens, et la solution mathématique du 1)
|
|
|
Bonjour Nicolaus Nous sommes bien d'accord le jeu d'échecs est "décidable", au sens logique du terme. Cependant ce sont les "propositions" qui sont décidables ou non !
Ainsi par exemple
la proposition : "Existe-t-il une stratégie gagnante pour les Blancs" est bien sûr décidable ;
cala veut dire qu'il existe une démonstration permettant d'affirmer que ceci est VRAI ou FAUX !
Mais la décidabilité n'est pas une démonstration.
Je maintiens fermement et en connaissance de cause qu'il n'existe aujourd'hui aucune "solution mathématique" au jeu d'échecs.
Cette solution consisterait, si elle existait, à fournir une stratégie gagnante pour les Blancs ou Une stratégie de nulle pour les Noirs
Mais je suis d'accord avec toi : c'est une chance pour notre jeu favori !
Michel
|
|
|
Pour info, Hardy (cf le premier lien) est vraiment pas une mazette en maths... Et il reste très vague sur le sujet :o)
Un autre mathématicien, amateur et moins célèbre, a dit : personne n'en sait rien.
Autre problème indécidable :
Les mathématiques trollesques ne sont-elles pas mieux adaptées pour démont(r)er la NTE ?
|
|
|
ref fleysour à partir du second lien on accède à l'Encyclopédie en lignes des suites de nombres entiers, c'est une petite merveille et un travail monstrueux !
|
|
|
ref Bruneau Michel ou Une stratégie gagnante pour les Noirs ... il y a 3 possibilités.
OK vous faites partie des gens qui pensent que les hommes ont inventé non seulement les mathématiques mais aussi leurs résultats, moi je suis de ceux qui pensent que les résultats mathématiques existent indépendemment et que l'on ne fait que les découvrir un moment ou à un autre, comme les Amériques pré-existaient à la 'découverte' de Christophe Colomb.
Ici je pense néanmoins que ce n'est pas une question de point de vue de philosophie sur la nature des mathématiques mais que l'affirmation "le jeu d'échecs est décidable" signifie que la solution du jeu d'échecs existe bel et bien (la décidabilité a été démontrée donc l'existence de cette solution aussi), mais seulement on est pas capable d'echiber la (ou les) solutions.
|
|
|
Oula non ! On peut souvent démontrer en théorie des jeux qu'une stratégie (gagnante ou de nulle) existe sans pour autant pouvoir l'exhiber ! De plus, je serais TRES surpris qu'il y ait moins d'étoiles dans l'univers que d'humains sur terre, en tout cas ce n'est pas ce que j'ai lu jusqu'ici, et de loin ...
|
|
|
'exhiber'
|
|
|
croisement avec Nicolaus
|
|
|
ref Cyrillev croisement :-)
|
|
|
Faux. Le nombre d'étoiles dans l'univers est largement supérieur à 2[28]. Il y a au moins 100 milliards de galaxies dans l'univers et une galaxie est composée en moyenne de 100 milliards d'étoiles.
|
|
|
croisement de croisement ;-)
|
|
|
mathématiques et jeu d'échecs En fait, j'ai lu en théorie des jeux que l'étude mathématique du jeu d'échecs n'a jamais vraiment "pris" : en effet, un tout petit changement dans les règles du jeu donne en principe un jeu qui n'a plus rien à voir avec le jeu "initial". Donc il y a peu de chance que, par exemple, la suite des "meilleurs coups à jouer" respecte une certaine loi mathématique.
|
|
|
Merci Fleysous ! Merci Fleysous pour les très bons liens !
Etant mathématicien et ayant travaillé dans le domaine de la théorie des nombres je connais G.H. Hardy et J.E.
Littlewood qui furent deux très grands
mathématiciens qui ont dominé leur époque dans les domaines ou ils ont travaillé.
Mon résultat est bien sûs plus faible que l'estimation de Hardy (extraordinaire), mais à le mérite d'être facilement abordable pour un joueur d'échecs non mathématicien.
Mon objectif était de mettre le doigt sur le fait que les échecs sont trop compliqués pour qu'on puisse en trouver une solution exhaustive, aussi bien par les mathématiques que par l'informatique.
Michel
|
|
|
Ce n'est qu'une question de temps L'informatique est un bébé.
|
|
|
ref Nicolaus çà veut dire quoi çà :"le jeu d'echecs est decidable!"mmhh?C'est un solecisme?
|
|
|
OK RenardBrun !! Ok je me suis en effet trompé concernant le nombre d'étoile, encore que toute estimation soit sujette à
caution en se domaine.
Il s'agit d'une erreur de traduction entre l'exponentielle de base 10 et celle de base 2 que j'utilise.
On trouve :
ici
10 à la puissance 23. D'autres spécialistes donnent une estimation comparable.
Donc je vais ce soir effectuer la modification sur mos site et adopter la
majoration :
2 à la puissance 72
Merci !!
Michel
|
|
|
ref michel Bruneau "decidable" au sens logique du terme:ben non le mot n'a pas de sens logique, eclaire moi.
|
|
|
ref nicolaus Le jeu d 'echecs n'est pas un jeu purement mathematique.Donc il ne faut pas lui chercher de solution mathematique.
|
|
|
non Laura Ce n'est pas qu'une question de temps pour l'informatique, c'est une impossibilité pure et simple, puisqu'il y a presque autant de positions légales que d'électrons dans l'univers, donc même en arrivant à adopter une stratégie de tables de Nalimov (qui supposeraient des stockages intermédiaires bien plus grands encore) et en arrivant à mettre une position et son résultat par électron, il faudrait utiliser tout l'univers comme stockage. Ce qui n'est pas facile, l'essentiel étant à des milliards d'années lumières.
|
|
|
ça me rappelle le poisson d'avril de chessbase il y a deux ans, "les tables de Nalimov pour 18 pièces sont disponibles" :)
|
|
|
Et le fait que le jeu d'echecs soit "decidable" ,cà te permet de le modeliser mathematiquement?
pour moi c 'est du Elisabeth Teissier ton propos.......
|
|
|
décidable... C'est bizarre d'employer des mots tels que "décidable" pour caractériser une fonction définie sur un ensemble fini... C'est un peu comme si on disait que l'eau est "humide" ! De même, l'algorithme de calcul du meilleur coup n'est PAS de complexité exponentielle car la profondeur max. de l'arbre de recherche est une constante (dépendant uniquement du jeu). Il est évidemment de complexité constante.
Sinon le grand nbre de parties possibles ne s'oppose en rien à l'existence d'un algorithme de calcul d'une meilleure stratégie en un temps acceptable (basé par ex. sur l'utilisation d'invariants).
Cordialement
Niko
|
|
|
Rontudju... Michel Bruneau, vous seriez mathématicien, et capable de pondre de telles absurdités ? :
La principale raison pour laquelle aujourd'hui l'informatique n'est pas apte à apporter une solution globale au problème des échecs par une voie théorique est qu'il existe des nombres échiquéens considérablement plus grands que tout nombre informatique
Quel fatras !
- 2^400, ce ne serait pas calculable informatiquement ?
- l'informatique ne pourrait apporter une solution globale par une voie théorique : késako ?
- De quoi parlez-vous : du calcul du nombre maximum de parties possibles, de la décidabilité du jeu, à savoir s'il existe une suite de coups les meilleurs possibles amenant à un résultat définitif ?
Il n'existerait aucune solution mathématique au jeu d'Echecs ???
Allons, le jeu est fini (i.e, il existe un nombre de coups maximal pour une partie), il existe donc une solution mathématique (au problème de la décidabilité, je suppose).
Ne pas savoir calculer ou déterminer une solution n'a jamais eu comme résultat en math, de dire que la solution n'existait pas !
Je suis sûrement un peu dur (de la feuille ?), mais mathématiques et rigueur sont plus que cousines.
Vous m'eûtes fait plus rire en prédisant l'avenir de quelqu'un à partir d'une position échiquéenne qu'il choisirait :o)
|
|
|
Elisabeth Teissier , je vous dit, à surement une opinion (peremptoire comme d'hab) là dessus.
|
|
|
a surement....
|
|
|
Si j'ai bien compris... On cherche à savoir si il est possible de connaître le nombre de positions (ou de parties) possibles, et de savoir dans quelle mesure on peut l'estimer, c'est bien ça ?
Mais le question que je me pose, c'est "est-ce que quelqu'un a déjà démontré qu'à l'heure actuelle il est possible de calculer précisément ce nombre ?" Ou combien de temps ça prendrait avec les algoritmes qu'on a pour l'instant.
Parce que je me rappelle vaguement qu'un jour notre prof de prepa nous avait démontré qu'il était pas possible de savoir quelque chose avec certitude (y avait un rapport avec e, pi et une histoire de rationnel mais je sais plus exactement ce que c'était).
|
|
|
Je m'escuse !!! Je voulais pô ! C'était plus fort que moi...
Par contre, j'en voudrais aussi de la même que vous prenez !
Un petit bijou
Une nulle de salon est une partie à la dynamique avortée, si je comprends bien ?
J'admire néanmoins votre courage face aux langues acérées du forum :o)
Bien triste pour elle, mais ainsi, elle ne pondra pas de théorie fumeuse à deux balles !
|
|
|
Arf, me suis mélangé les pinceaux ! Elle était trop bonne !
Une nulle de salon est une partie à la dynamique avortée, si je comprends bien ?
Bien triste pour elle, mais ainsi, elle ne pondra pas de théorie fumeuse à deux balles !
J'admire néanmoins votre courage face aux langues acérées du forum :o)
|
|
|
Réponse à Nirnaeth Bonjour !
Intervenir sur FE me maintient jeune ... C'est pour moi (je sais de quoi je parle j'interviens sur une dizaine de forums en français ou en anglais) le plus vivant et le plus intéressant de tous les forums du monde !
Mais alors c'est pas la tranquillité du tout :-)))))))))
Je vais répondre sur deux points et dans un autre message je répondrai sur la décidabilité !
Au sujet de 2 à la puissance 400 je dis bien dans mon texte que je ne parle que de nombres intervenant en tant que paramètres . A titre d'exemple 50 est un petit nombre mais un système mécanique à 50 degrès de liberté est vraiment très difficile à étudier.
On sait très bien aujourd'hui que les problèmes à 6 pièces, sans pions, sont totalement résolus. Parce que là les paramètres qui interviennent sont beaucoup plus petits.
Je poste ça et je continue !!
Michel
|
|
|
Réponse à Nirnaeth II Du point de vue des mathématiques les échecs se présentent très mal ! D'une part on ne peut pas procéder au cas par cas, pour épuiser le sujet, comme l'orsqu'on a affaire à des petits nombres, d'autre part on ne peut pas utiliser les puissantes méthodes de l'analyse qui valent lorsque les paramètres qui interviennent peuvent
être identifiés à l'infini.
A cette première raison s'en ajoute une seconde comme je l'explique sur mon site : Le jeu d'échecs est trop particulier pour le mathématicien : Pourquoi 64
cases et pas 200 ? Pourquoi 2 Dames et pas 7 ? etc ...
Pour traiter le problème mathématiquement il faudrait dire :
soit un jeu à n joueurs comprenant un échiquier à x case et y pièces de z sortes différentes etc ... Ce serait dingue !
Michel
|
|
|
En vrac 1. La solution mathématiques au jeu d'échecs existe. Je n'ai pas besoin de fournir cette solution pour prouver qu'elle existe.
2. L'impossibilité de trouver effectivement la solution n'est pas un problème de mémoire, mais de temps. On peut explorer l'arbre des coups possibles sans le mémoriser, mais en construisant les branches au fur et à mesure (et sans les conserver, bien sûr).
|
|
|
c profond :P Tout d'abord, je peux te confirmer que le nombre de parties valides et supérieur à 2^400. Demonstration facile pour l'AF4 que je suis: repéter trois fois la même position ne donne la nulle que si un des joueurs le demande. Donc je prends une position avec échec perpetuel et j'ai comme parties: celle où la nulle est demandée après 3 repétitions, après 4 repétitions, après 5 repétitions etc. :-)
Ce n'est pas pour faire le malin, mais juste pour accentuer le fait que ce qui compte pour évaluer la profondeur des échecs n'est pas le nombre de parties possibles, mais le nombre de positions possibles. Déjà dans les ouvertures il y a plein de transpositions possibles, et pour arriver à roi et pion contre roi, il y a pas mal de possibilités.
Estimons le nombre de positions possibles. Je prends un échiquier et 32 pièces. Je place ma première pièce: 64 possibilités. Deuxième pièce: 63 possibilites etc. Ca me fait 64*63*...*33 = 64!/32! .
En utilisant la formule de Sterling (en gros ln(n!)=n*ln(n)), j'ai: 64! = 2^296 et 32! = 2^117. Donc j'ai 2^(296-117) = 2^179 possibilités. Le nombre est trop grand pour deux raisons:
1° J'ai compté les positions illegales comme les deux rois en échec, pions blancs sur la première rangée etc.
2° Je n'ai pas tenu compte du fait qu'il y a des pièces identiques. Que je place le premier pion blanc en a2 et le deuxième en b2 où l'envers, ça donne la même position. Or, j'ai compté les deux possibilités.
Pour corriger 1°: je ne sais pas comment faire.
Pour corriger 2°: il faut diviser par (8!*2!*2!*2!)^2 (8 pions, 2 cavaliers, deux fous et deux tours identiques, et ça pour les deux couleurs).
Donc mon estimation pour le nombre de positions avec 32 pièces (puisque (8!*2!*2!*2!)^2 = 2^37):
2^(179-37) = 2^142,
ou, en système décimale:
10^43.
Bien sur, après il faut compter le nombre de positions avec 31 pièces, 30 pièces etc., mais ça ne change guère le logarithme. Donc pour résoudre les échecs par ordinateur, il faudrait un ordinateur avec une mémoire d'environ 10^45 bits. Pour le moment pas faisable. Un chiffre pour comparer: masse de la terre environ 10^25 kg.
En conclusion: les échecs sont profonds, mais les chiffres qui sont donnés habituellement (en général supérieur au nombre d'atomes dans l'univers) sont éxagerés.
|
|
|
En tout cas, on devrait décider que ça reste un jeu Grosso modo, la décidabilité repose sur la possibilité pour une proposition mathématique
d'être validée (vrai ou faux) par un algorithme.
Si l'on considère la proposition mathématique : "d2 - d4 est un meilleur coup que a2 - a4 si je veux avoir des meilleures chances de gagner", le calcul de ce prédicat est à la portée du premier golmon venu. Les joueurs d'échecs chevronnés préférant certes utiliser Fritz.
Donc, il est possible de considérer que le jeu d'échecs est décidable en fonction de la proposition posée.
Par contre, dans la mesure où il existe une infinité de propositions possibles dans le jeu d'échecs, eu égard à sa combinatoire (allez démontrer le contraire, je pose un lemme), vous allez certes avoir du mal à tout décider.
Enfin, toute décidabilité est-elle absolue ? Et à quoi servent les théorèmes ? Les mathématiques s'accomodent fort bien d'une certaine incomplétude, contrairement aux tenants de l'opposition entre sciences molles et dures, laquelle relève d'une pensée nullitaire.
j'en profite pour caser un corrigé d'oral de math d'entrée à une grande école, que j'ai fait récemment (sans bouquins et avant de vérifier sur internet), adapté pour créer une blague ingénieur :
On suppose un couple fécond mais sans naissances multipares
Soit p la probabilité d'avoir un ingénieur grande école math sup' math spé
Soit q la probabilité d'avoir un débile
Bien évidemment,
p = 1 - q
q=1-p
On pose dans le cas d'espèce p=q=0.5
p=1-p
q=1-q
Le couple décide de procréer jusqu'à ce qu'il ait un ingénieur.
Soit N le nombre de débiles obtenus successivement.
Soit X le nombre total de mioches pondus.
Il va de soi que X= 1+N et X-N= 1 et N=X-1, avec N dans l'intervalle [0 ; + l'infini, puisque si le premier-né est un ingénieur, le couple s'en contentera.
Soit k le nombre possible (variable) de mioches,
La probabilité P(X=k) pour tout k est nécessairement une fonction de résultat géométrique décroissant compte tenu des paramètres postulés, car intuitivement nous voyons que nous travaillons en puissances de p et q, et que p=q=0.5.
P(X=k) = (p^(k-1))q^1 = (p^(k-1))q
Puisque q^1 correspond à l'événement qui met fin à la comédie, et que donc il y aura nécessairement k-1 débiles dans la " réussite " du projet.
Intuitivement, si on a 0.5 chances d'avoir un débile, la chance d'avoir un 2ème débile sera le produit des probabilités de ces événements indépendants. Dans l'hypothèse équiprobable, on travaille donc manifestement en puissances naturelles de 0.5 !
Après coup, je constate que c'est la loi géométrique, que je n'avais jamais apprise.
Compte tenu des égalités postulées, on a aussi P(X=k) = (p^(k-1))(1-p) = p^(k-1)- p^k
Quant à connaître le nombre de mioches k° pondus tel que la probabilité que le nombre de débiles procréés lui soit AU PLUS égal, soit >= 0,95, essayons de traduire le problème plus simplement :
Si N=k°, le " contrat " n'est pas rempli, le couple va continuer de jouer au con !
(*) De ce qui précède, (P(N=k) pour tout k) = p^k
P(N=0.95 équivaut à :
P(N=k°) k ! Donc, pas la peine de raisonner sur N>=k)
P(N=k°)
|
|
|
Chuis encore désolé... Paramètre, j'ai du mal à comprendre... C'est pour dire qu'il y en a beaucoup ?
Moi, tout ce que je saurais faire mathématiquement, ce serait soit de trouver une formule de calcul, soit d'estimer une majoration, (et/ou une minoration) au nombre de parties possibles, et dans ce cas précis, ce n'est pas simple...
2^400 : c'est génial comme résultat, mais estimer une limite à partir d'une moyenne, ça ne marche pas...
On avait essayé d'estimer, dans un autre post, le nombre maximal de coups pour une partie, (en respectant les règles de la Fide), ça tournait entre 5 et 10000 coups !
Il va de soi que le nombre de parties de 40 coups au plus n'est alors qu'une petite partie du nombre total de parties.
On peut donc affiner votre formule, E = (2^10)^Nombre max de coups/2, allez à la louche 2^50000.
Ce qui ne signifie bien sûr rien mathématiquement, et me semble suffisamment éloigné de l'estimation de Hardy pour avoir un doute sur la validité du calcul :o)
On est tous d'accord sur l'impossibilité physique de calculer toutes les parties, voire même toutes les positions.
Un tour de force mathématique serait de borner entre quelques ordres de grandeur, of course) le nombre de parties possibles... Et cela demande beaucoup plus de compétences mathématiques que je n'en ai !
|
|
|
suite (P(N=k°)inf=0.05)
Équivaut à (*) : p^k°inf= 0.05
Comme p^k est décroissante pour 0 inf p inf 1, avec k naturel dans la nature, le " pivot " k° est donc tel que p^k°= 0.05
Cela revient à dire que 0.5^k° =0.05 ou encore que (1/2)^k° = 1/20, ou encore 2^k°=20,
Donc k° = INV(20²), la calculette donne une première approximation fausse en raison de sa faible précision, affinée par calcul et vérifications triviales à environ 4,3, donc " dans le vrai " à 5 puisque que le nombre d'enfants d'un couple appartient à l'ensemble des entiers naturels, même si les statisticiens nous découpent tout ça sans remord.
Comme tout ça c'est des bêtes probabilités, j'en connais qui ont fait plein de débiles et d'ingénieurs !
Mais savoir si l'assertion "un ingénieur n'est jamais débile" est vraie, est-ce bien décidable ;-) ?
|
|
|
suite à pb copie-coller
|
|
|
Réponse à réponse à Nirnaeth II Roh, le particularisme en math sert quand même un peu !
Je préfère quand même résoudre une équation du deuxième degré que trouver une solution génèrale à une équation de degré n...
Le jeu d'échecs n'est pas trop particulier pour le mathématicien, mais trop complexe à modéliser.
|
|
|
calcul bis Les ordinateurs actuels ont une mémoire de quelques centaines Go, donc disons 10^15 bits. Pour résoudre les échecs, il faudrait alors un ordianteur 10^30 fois plus puissant (puisque le nombre de positions possibles et à peu près 10^45). 10^30 et à peu près égal à 2^100. Donc si les ordinateurs doublent leur puissance tous les cinq ans, les échecs seront résolu par l'ordinateur dans environ cinq siècles.
|
|
|
A tous ! Je reviendrez demain sur FE, dans ce fil, car plusieurs de vos remarques sont très intéressante ... mais ce soir j'ai des rectiifications à faire sur mon site.
C'est idiot mais je viens seulement de trouver le truc pour signifier 2^400 !
A+ Michel
|
|
|
Ref Versatile Elle est décidable (falsifiable) si l'on trouve un ingénieur débile. Et c'est assez trivial.
L'assertion "un ingénieur est toujours débile" est beaucoup plus dure à falsifier :o)
|
|
|
Je corrige :-((((((((( Je reviendrai demain sur FE, dans ce fil, car plusieurs de vos remarques sont très intéressantes etc ....
|
|
|
Il est sérieux, le bougre... Autre problème mathématique :
Démontrer que la probabilité de raisonner un mathématicien génial que sa "théorie" est foireuse est inférieure à 1/2^400
|
|
|
Blague à 1/2^400 € qui tombe à la baille :o) Démontrer que la probabilité de convaincre un mathématicien génial que sa "théorie" est foireuse est inférieure à 1/2^400
|
|
|
et on s'amuse encore Combien de parties d'échecs différentes est-il possible de jouer ?
n'est pas un prédicat correctement formulé, donc vous ne risquez pas de d'évaluer sa décidabilité. Une question ne peut être un prédicat.
On pourrait le traduire de façon plus rigoureuse par, par ex. :
"le nombre de parties d'échecs différentes d'au moins un mouvement de pièce a pour majorant l'infini".
Il est d'autant plus probable de considérer ce prédicat vrai si on part de la réalité bestialement mathématique suivante :
Hormis la règle selon laquelle la partie est nulle si 50 coups sont joués sans prise et sans mouvement de pion, une partie :
- n'est pas théoriquement limitée par son nombre de coups tant que l'on respecte les règles liées aux cas de nulle (mais est-on obligé de réclamer la nulle ? ;-),
Donc si on omet le nombre de coups physiquement réalisables par un joueur normal en, par exemple, 2 heures...Sachant que la variable t (définie par l'instant de la fin d'une partie) du temps inclu dans le temps imparti s'apparente aux réels,
L'infinité de coups possibles suffit à rendre trivialement parfaitement décidable le prédicat, sans même parler de leur nature qualitative, aussi absurde cela puisse paraître concrètement.
- On remarquera que le fait que tout joueur a le droit d'abandonner à n'importe quel instant d'une partie de n coups, n tendant théoriquement vers l'infini, aggrave le cas ;-)
j'ai peut-être émis un sophisme, mais c'est amusant.
|
|
|
Ref Versatile Dans ce problème, si l'on veut éviter l'infini, on postule que :
- la règle des 50 coups s'applique systématiquement.
- que 3 fois la même position termine la partie.
Question (simple :o)) : avec ces conventions, quelle est la plus longue partie possible ?
|
|
|
autour de 5899 coups.
Sur le fond, niko a évidemment raison.
|
|
|
Forcément, il doit exister une formule mathématique applicable au jeu d' échecs pour trouver le/les coups parfaits (nulle,gain ou perte).
Les échecs sont comme l' astrologie: ça aspire à devenir une science exacte.
La méthode russe s' informatise avec les tables de 6 pièces...
Perso, je préfère de plus en plus regardez des parties propres (correspondance, ou celles que jouent Hydra).
La fantaisie aux échecs se doit d' être mieux défini ;-)
|
|
|
tient, 1/2^400? C'est justement la proportions de propos intéligents tenus par Polymagoo.
|
|
|
Petite colle : L'affirmation suivante de Versatile est fausse :
"la partie est nulle si 50 coups sont joués sans prise et sans mouvement de pion."
Pourquoi ? (la solution est pas qu'il faut en referer a l'arbitre).
|
|
|
et ? ou ou ?
|
|
|
Ben s'il y a mat au 50e coup ...
|
|
|
Mais Bellamy Si on ne mémorise pas les branches (ou au moins le résultat d'une position donnée), on ne résout pas le jeu. On a tout exploré mais on ne sait pas si sur un jeu optimal c'est gain ou nulle.
|
|
|
ref Versatile c'est justement à une question que se réfère la décidabilité et non à un prédicat. Un prédicat est soit vrai soit faux.
Exemples :
"Combien puis-je acheté de bonbons à 5 cents avec N euros ?" est un problème décidable du moment que l'on connait N.
Le prédicat "Windows est un bon système d'exploitation" est faux.
|
|
|
Ref Nicolas Pas réveillé, c'est bien 'et'...
Outre, la condition de Cyrillev, 50 coups consécutifs ?
|
|
|
Ref Cyrillev Si l'on veut résoudre le jeu, il faut explorer le coup 1.a3, le coup 1.a4, etc...
Si on s'aperçoit que le coup 1.a3 conduit à la nulle, c'est seulement cette information qu'il faut conserver avant de passer à a4, et pas l'arbre découlant de 1.a3. Inversement, je n'ai pas besoin de construire l'arbre découlant de 1.a4 pour explorer 1.a3.
Mais cela se retrouve à tout les niveaux de profondeur. Si pour explorer 1.a3 a5, je n'ai pas besoin de 1.a3 a6, etc...
En fait, la quantité de mémoire nécessaire est en gros proportionnel au nombre de coups de la partie.
|
|
|
Mais pour conclure ça Il faut stocker (au moins le temps du calcul) les résultats de toutes les branches en découlant pour pouvoir remonter! Et là c'est encore bien pire qu'avec une approche Nalimov, parce qu'il faudrait à l'optimal retenir le résultat de chacune des positions qui peuvent survenir en la moitié du nombre de coups moyen des parties -et donc même en se limitant aux parties de 40 coups, il y a environ 10 puissance 60 parties de 20 coups, donc avant même de commencer à les analyser, leur simple recensement demande 10 puissance 60 fois l'espace pour une partie de 20 coups (il faut garder l'arbre qui y a mené sinon on ne peut pas non plus conclure).
|
|
|
il me semble que Je ne vois pas de démonstration du 1) Même si on invoque de grands nombres pour quantifier le nombre de parties possibles, je ne trouve pas évident (et c'est un euphémisme) que cela montre qu'il ne peut pas exister de solution mathématique au jeu. D'autre part, le calcul ne tient pas compte des transpositions, ni du fait que de nombreuses branches sont sans intérêt (parce que la conclusion est évidente et tout calcul ultérieur inutile): il n'est donc peut-être pas utile d'identifier toutes les positions possibles à partir d'une position donnée pour arriver à une conclusion certaine sur l'issue de la partie avec le meilleur jeu adverse. Les grands nombres en prennent un coup.
Mais tous les programmeurs de logiciels d'échecs savent tout cela depuis longtemps, non ?
|
|
|
Mais alors on quitte la démonstration pour entrer dans l'estimation. Et là la réponse est claire : sur un jeu parfait il y a nulle !
|
|
|
ref azertyqsdf
oui tu as raison mais le nombre de parties "cohérentes" qu'il reste est toujours énorme ... l'ordre de grandeur donné n'est qu'une borne inférieure de toute façon.
L'important du point de vue théorique est que ce nombre (bien que non "humain") est fini donc toutes les parties sont explorables dans l'absolu... c'est le résultat de décidabilité.
ref Nirnaeth
J'ai mis un moment à comprendre à quoi tu fais allusion ... le problème des fautes d'orthographe dans un texte est un problème également décidable mais très difficile à vérifier par un humain donc étant donné que le nombre de post est limité à 200 ("plus ce que voudra bien donné le 4ème arbitre comme temps additionnel") pour un sujet donné, il semble donc raisonnable en première approximation de NE PAS SIGNALER TOUTES LES FAUTES D'ORTHOGRAPHE.
|
|
|
A propos de la décidabilité Lorsque je dis qu'il n'y a pas de solution mathématique ou informatique au jeu d'échecs, je me place du point de vue effectif et non theorique ; ainsi ce que je dis n'a aucun rapport avec la décidabilité.
Cela va m'obliger à modifier un peu la formulation de mes questions pour les rendre plus claires.
Reste que le problème de la décidabilité est intéressant et que les idées exprimées par les uns ou les autres ici à ce sujet ne sont pas toujours très claires.
Le grand mathématicien Allemand David Hilbert a tenté vers la fin de sa vie, à partir de l'axiomatique, de bâtir une théorie formaliste des mathématiques s'appuyant sur la conviction que toute proposition est décidable
Or en 1931 Kurt Gödel, mathématicien américain d'origine autrichienne, a démontré le théorème d'incomplétude
qui ruinait les espoirs de Hilbert.
Pour en revenir aux échecs, il est vrai que toute théorie finie est décidable et que les échecs relèvent bien d'une telle thèorie.
Tout cela est un peu long à expliquer ici et je vais traiter cette question à fond dans une autre page de
"Chess Theory".
A+ Michel
|
|
|
Le théorème de Gödel Pour ceux que ça intéresse le théorème d'incomplétude de Gödel"
s'ennonce ainsi :
Dans toute théorie non contradictoire, assez riche pour contenir l'arithmétique, il existe nécessairement des propositions indécidables.
A+ Michel
|
|
|
Ref : Michle Bruneau : simplechess a bien raison de signifier que ce qui compte si l'on veut se placer du point de vue "résolution du jeu", c'est le nombre de positions légales possibles et non le nombre de parties possibles (qui ne signifie pas grand chose).
Pour illustrer ce propos, notons que c'est cette approche du nombre de positions possibles qui est utilisée pour construire les tables de 6 pièces :
1.On dénombre l'ensemble des positions légales possibles.
2. on inventorie toutes les positions "mortes" (mat ou nulle a cause du matériel ou pat)
3. par itérations successives on en déduit le résultat pour toutes les positions proches de 1 coup (du style une position ou c'est mat en 1, ou nulle en 1), puis on fait de même pour 2 .....
On a ainsi construit une sorte d'arbre ou toutes les positions à 5,6 pièces sont déterminées ( nulles ou gagnantes ).
Voila pourquoi l'estimation donnée par simplechess de 10^45 est plus exploitable du point de vue de la "résolution du jeu" que les "2^400 = 10^120 ! parties possibles qui ne signifient pas grand chose ........
|
|
|
par ailleurs, l'apport de Bellamy est également très intéressant : si on veut décider si le jeu est nul, ou gagnant à partir de la position de départ, nul besoin de stocker l'ensemble des branches explorées, mais il suffit de stocker l'évaluation des branches.
Cependant, si on veut non seulement l'évaluation mais en plus la stratégie correcte, la il faudra évidemment stocker ces fameuses 10^45 positions possibles, avec pour chaque position l'évaluation de l'ensemble des coups légaux disponibles ! Et la on y coupera pas ..... ( encore une fois c'est la meme approche que les tables de Nalimov 5,6 pièces)
|
|
|
Euh... Pour en revenir aux échecs, il est vrai que toute théorie finie est décidable et que les échecs relèvent bien d'une telle thèorie.
Dans toute théorie non contradictoire, assez riche pour contenir l'arithmétique, il existe nécessairement des propositions indécidables.
Ces deux prédicats ne sont-ils pas contradictoires ?
Sauf à penser qu'il existe des axiomes contradictoires aux Echecs ?
Ref Nicolaus (et M. Bruneau) : la décidabilité, sauf erreur de ma part, c'est de pouvoir démontrer un résultat (théorème), à partir d'un algorithme et d'hypothèses de départ (axiomes).
Ce qu'a montré Gödel, c'est que s'il n'y a pas d'axiomes contradictoires, il existe des thèorèmes non démontrables. Et si tous les thèorèmes possibles de la théorie sont démontrables, alors il y a des axiomes contradictoires.
A vérifier quand même, parce que ce que démontre Gödel n'est pas si trivial, et j'ai pu me planter.
Pour en revenir aux Echecs, l'algorithme permettant d'aboutir à un résultat définitif est simple à écrire :
C'est du min-max développé jusqu'à la fin.
Donc l'algo existe, donc le jeu doit être décidable.
Par contre, il est clair que cet algo est inappliquable et que le "résultat final" du jeu n'est pas accessible.
|
|
|
Cyrillev sur un jeu parfait il y a nulle
Tu peux le démontrer ? :) Je peux admettre que les noirs ne gagnent pas (il suffit de montrer que les blancs perdent un temps, et négliger les possibilités de zugzwang au 1er coup :) ), mais que les blancs ne sont pas gagnants, ca je ne le sais pas.
|
|
|
Ref Nirnaeth "Ces deux prédicats ne sont-ils pas contradictoires ?".
1) Il faut distinguer "proposition" et "prédicat". "Etre décidable" est un prédicat, "Les Echecs sont décidables" est une proposition.
2) Il n'y a pas de contradiction. L'arithmétique est évidemment une théorie infinie (nb infini de formules possibles) alors qu'il n'y a qu'un nb fini de positions différentes aux Echecs. Parler de la décidabilité (ou de l'indécidabilité) de la première a un sens, parler de la décidabilité du second est une trivialité. Evidemment les Echecs ne contiennent pas l'arithmétique !
"Ce qu'a montré Gödel, c'est que s'il n'y a pas d'axiomes contradictoires, il existe des thèorèmes non démontrables".
Non. Il a montré que si la théorie (théorie = axiomes + règles de déduction) est *suffisamment expressive* (contient l'arithmétique) alors soit elle est contradictoire (i.e. il existe A tel que on peut montrer A et non A) soit elle est indécidable (i.e. il existe A pour lequel on ne peut démontrer ni A ni non A). De manière schématique l'idée est de coder la vérité d'une proposition P dans la théorie elle-même. Alors il devient possible d'écrire une proposition P telle que P est vrai ssi non(P) est vrai d'où le résultat.
Par exemple supposons qu'on dispose d'un ordinateur capable de répondre à toutes les questions de manière exacte. Alors il suffit de lui poser la question: "L'ordinateur répondra-t-il non à la question que je suis en train de poser ?". Si l'ordinateur répond oui, sa réponse n'est pas exacte. S'il répond non elle ne l'est pas non plus. D'où pb.
Cordialement, Niko
|
|
|
oops "soit elle est indécidable"
incomplète, pardon !
A+
Niko
|
|
|
Ref Niko Merci !
Ok, je me comprends mieux, et cela résoud la petite incohérence qui me turlupinait :
Les Echecs sont consistants (on ne peut démontrer une chose et son contraire) et complets (on peut démontrer tous les formules vraies), car formellement insuffisament complexe.
Donc l'une des trois formules "les blancs gagnent sur le meilleur jeu", ou les noirs, ou partie nulle est vraie et démontrable.
Je bute encore sur le fini...
Pour les Echces, il me semble trivial que c'est la finitude qui permet d'assurer la validité d'une des trois formules.
Il existe des systèmes infinis complets (Gödel joue aux allumettes
|
|
|
Alors je vais me répéter "on quitte la démonstration pour entrer dans l'estimation. Et là la réponse est claire : sur un jeu parfait il y a nulle !" Inutile après ça de me demander de le démontrer, puisque j'ai dit que c'était parce qu'on quittait le domaine de la démonstration que je disais ça.
|
|
|
Ref Nirnaeth et Ciyrillev Il faut bien sur que les 50 coups soient consecutifs et n'aboutissent pas au mat.
br>
Mais il y a autre chose qu'on oublie en general : 50 coups sans roque !
|
|
|
Ref Nicolas Oulà, je suis un peu surpris...
Le 9.3 de la feufeufeu ne parle pas du roque dans la règle des 50 coups...
|
|
|
50 coups sans roque ? Sans blague ? Ou ca ? Je t'aide, voici le texte de l'article des
FIDE Laws of Chess
9.3 The game is drawn, upon a correct claim by the player having the move, if
a. he writes on his scoresheet, and declares to the arbiter his intention to make a move which shall result in the last 50 moves having been made by each player without the movement of any pawn and without the capture of any piece, or
b. the last 50 consecutive moves have been made by each player without the movement of any pawn and without the capture of any piece.
|
|
|
Je vais répondre ! Il y a tellement de remarques intéressantes que je vais répondre à chacun ... au moins dans la journée !
Michel
|
|
|
Réponse à Oopi Oui tes deux posts sont intéressants et c'est bien vrai que considérer le nombre de positions plutôt que le nombre de parties peut présenter en soi un intérêt.
On dispose d'ailleurs d'une très bonne estimation qui est celle de Shannon (1950) au sujet du nombre de positions possibles après 40 coups :
10^43.
Moi je me suis placé d'un point de vue différent consistant à étudier le déroulement d'une partie concrète. C'est un point de vue qui m'intéresse et je continuerai certainement dans cette voie.
Michel
|
|
|
Réponse à Nirnaeth : Euh... Non il n'y a pas de contradiction ! Explications :
l'arithmétique est une théorie mathématique, encore appelée Théorie des nombres basée sur l'axiomatique de Péano. Notons A cette théorie.
Si une théorie T contient A elle contient forcément tous les nombres entiers, donc elle est infinie
Pour ce qui concerne les échecs, il faut imposer des règles comme la règle des 3 coups et la règle des 50 coups pour obtenir une majoration absolue du nombre de coups. Donc du nombre de parties possibles.
Sous les conditions précédentes les deux propositions suivantes sont décidables :
(autrement dit on peut affirmer que l'une est vraie et l'autre est fausse :
(P) Les Blancs ont une stratégie de gain
(non P) Les Noirs ont une stratégie qui annule ou à la limite qui gagne, mais c'est bien peu probable.
Michel
|
|
|
Rép. à rép. à Rép à Nirnaeth II Je suis vraiment d'accord avec beaucoup de choses que tu dis !!...
Sur ce point je crois même que ta formulation est peut-être meilleure que la mienne. Il est vrai qu'en mathématique un paramètre entier particulier comme par exemple n=3 (espace euclidien) ou n=4 (variété riemanniene de dimension 4) peut présenter un très grand intérêt.
Ainsi pour les jeux de table se limiter, dans un premier temps d'étude, aux jeux à n=2 joueurs semble raisonnable !
Mais pour décrire le jeu d'échecs complètement il faut faire intervenir un nombre de paramètre incroyable (nombre de cases, position des pièces, déplacement des pièces, règles du jeu !!! etc ...)
C'est donc bien la complexité du jeu qui le rend pratiquement inabordable pour un mathématicien !
Michel
|
|
|
Ref Michel Sur (non P), c'est bien peu probable :
Non !
Il n'y a aucune raison, à priori, que les noirs ne gagnent pas...
Le premier coup des blancs, comme dans d'autres jeux, n'est peut-être qu'une dégradation irrémédiable de leur position.
Il ne faut pas tenir compte de la pratique (Blancs commencent implique petit avantage) dans ce cadre où l'on s'occupe de la résolution absolue du jeu (qui semble totalement impossible, je le redis).
Sur ton deuxième post : même le calcul du nombre de parties possibles de n coups devient rapidement inextricable...
Donc on revient au trivial "on n'en sait rien" :o)
Le seul truc mathématiquement valable serait de dire qu'un majorant du nombre de parties possibles est la somme des degrés maximum de liberté de chaque pièce (4 pour un pion, 8 pour un roi au centre, 8 pour le C, etc...), au carré, à la puissance nombre maximum de coups possible...
Bref, encore un résultat qui va faire trembler les maths et les Echecs !o)
|
|
|
Réponse à PollyMagoo @ bruneaumichel par PollyMagoo
/ théorème de Godel, comment définir : thèorie non contradictoire ? et, en fin de ta déf' : " il n'existe pas de propositions décidables " me paraît plus clair..?!
Une théorie mathématique est non contradictoire s'il n'existe pas au moins une proposition (P) telle que (P) et (non P) soient des théorèmes de cette théorie.
La grande difficulté est qu'il est impossible de démontrer qu'une théorie importante, comme justement l'ensemble de toutes les mathématiques, est non contradictoire.
On a la conviction et non la preuve formelle que les mathématiques sont non contradictoires !!
Quant à la conclusion du théorème de Gödel, il est impossible de l'interpréter comme tu le fais. En effet
1°) Tout théorème est une proprosition vraie, donc forcément décidable.
2°) Les mathématiques modernes contiennent l'arithmétique si bien qu'il existe des propositions mathématiques non décidables.
3°) La méthode de Gödel, dans une théorie T contenant l'arithmétique, consiste à construire une proposition (I) signifant (I n'est pas décidable).
Ainsi si (I) est FAUX la théorie T est contradictoire puisque (I) est à la fois décidable (puisque faux) et non décidable (par définition).
Supposons maintenant que la théorie T est non contradictoire. Alors (I) ne peut pas être FAUX compte tenu de ce qui précéde. Mais (I) ne peut pas non plus être VRAI, car alors (I) serait décidable ce qui serait contradictoire. Donc (I) est non décidable.
Quand à la démonstration elle est très compliquée ! .... Et j'avoue ne l'avoir jamais lue !
Michel
|
|
|
Ref : Nirnaeth Ton dernier message comporte une remaque très juste concernant (non P), que j'ai mal formulé :-(((((((((
Il semble évident que disposer du trait est un avantage, et pourtant ce n'est pas formellement prouvé !
Ainsi l'idée, comme je l'ai lu ici je crois, que les Blancs sont en zugzwang dès l'ouverture à considérer.
Michel
|
|
|
"Pour ce qui concerne les échecs, il faut imposer des règles comme la règle des 3 coups et la règle des 50 coups pour obtenir une majoration absolue du nombre de coups. Donc du nombre de parties possibles."
Même si on oublie ces deux règles le nbre de *positions* possibles reste fini. C'est tout ce qui importe.
Cela dit le nbre de pos. n'a rien à voir avec la difficulté du jeu: il existe des jeux contenant un nbre de positions bien plus important (voire infini) qui peuvent être résolu de manière triviale (des jeux avec un nbre de positions très faible sont triviaux, mais la réciproque n'est pas vraie).
"Sous les conditions précédentes les deux propositions suivantes sont décidables :
Cela n'a STRICTEMENT AUCUN SENS de parler d'une "proposition décidable". Toute proposition (prise isolément) est trivialement "décidable" au sens ou il existe un algorithme qui indique si elle est vrai ou non (l'algorithme en question est soit return(true) soit return(false)).
Cela a un sens de dire "une proposition P est prouvable (ou non prouvable) dans un système formel X".
Cela a du sens de parler de décidabilité que pour un ensemble infini (ou par extention une fonction).
Cordialement, Niko
|
|
|
Oui & Non Niko ! Cela a un sens de dire qu'une proposition es décidable dans le cadre d'une théorie T
Ainsi cela a un sens de dire que les échecs constituent à eux seul une théorie mathématique E, les règles du jeu remplissant le rôle d'axiomes.
Dans la théorie E le théorème de Gödel ne s'applique et il est qu'il existe un algorithme permettant, du moins
théoriquement, de répondre à toute question que l'on se pose. Ainsi :
Dans la théorie E :
(P) : "Les Blancs ont une stratégie de gain" est décidable.
A+ Michel
|
|
|
"Décidable" veut bien dire "prouvable" Dernière précision : décidable veut bien dire prouvable
|
|
|
non "décidable veut bien dire prouvable"
Non, en tout cas pas dans l'acceptation couramment admise de ces deux termes.
En ce qui concerne la "théorie E" donner les axiomes ne suffit pas à la caractériser: il faut encore préciser la syntaxe des formules et les règles de déduction avant de pouvoir parler de prouvabilité.
Le + naturel, si on veut parler d'une "théorie du jeu d'Echecs" (ou de tout jeu similaire) est de considérer que toute formule est de la forme "Blanc/Noir gagne/perd/ne gagne pas/ne perd pas dans p" où p est une position. Alors les axiomes sont les position de mat ou de pat et les règles de déduction les règles de déplacement des pièces. La décidabilité est triviale (nbre de formules fini) et la théorie est évidemment cohérente et complète.
Cordialement,
Niko
|
|
|
Bon j'ai pas tout lu en details, j'interviens juste pour dire qu'il existe une enorme difference (du moins en maths) entre "decidable" et "prouvable".
La meilleure preuve est qu'il existe, dans les systemes axiomatiques classiques (ie Zermelo-Fraenckel), des enonces qui sont vrais (donc a fortiori decidables) mais pas prouvables !
Evidemment ca va paraitre extremement etrange a ceux qui maitrisent mal les arnaques de la Logique (dont je fais d'ailleurs partie), mais j'y peux rien, c'est comme ca...
|
|
|
je me permets de relancer ce fil car perso je ne comprends pas la différence entre "décidable" et "prouvable". Quelqu'un (nico dupont par exemple) pourrait me l'expliquer ?
Voici pour l'instant où j'en suis : "décidable" dans un système formel donné, cela signifie qu'on a les moyens de répondre à la question "la formule est-elle vraie ?" en utilisant les axiomes de ce système formel. "Prouvable" dans un système formel donné, cela veut dire qu'on peut déduire la proposition des axiomes du système. Je n'arrive pas à voir de différence.
|
|
|
notamment je m'interroge sur la phrase "des énoncés qui sont vrais (donc a fortiori décidables) mais pas prouvables."
|
|
|
Fox, je te scanne et t'envoie ... un truc dès que j'ai le temps ....
En gros demain soir ou Dimanche ...
|
|
|
en rapport avec ta question of course ! ;o)
|
|
|
ok merci ;-)
|
|
|
C'est parti ! Bonne lecture ! ;o)
|
|
|
merci beaucoup pour toutes les pages scannées mais après lecture je m'aperçois que je savais déjà tout ce qui était dans l'article. Pour autant je ne comprends toujours pas la différence, pour une proposition vraie et un système formel donnés, entre le fait d'être décidable (à l'intérieur du système) et d'être démontrable (à l'intérieur du système).
|
|
|
J'ai lu un autre article où cette différence ... était clairement montrée, mais je ne le retrouve pas pour l'instant.
Je continue à chercher .... ;o)
|
|
|
