Syracuse et langton

[invite84127968]

Dans une vidéo vue sur Futura ou l'on parle des conjectures en général, il y a la description de la conjecture de Syracuse, cette vidéo m'a tout de suite projeté vers l’algorithme de Langton (Il y a quelque temps j'ai eu l'idée de chercher de faire sortir d'une spirale d'ULAM la fourmi de Langton: considérer la grille de la fourmi comme la spirale d'Ulam et noircir les cases des nombres premiers. J'ai écris spirales car dans mon idée la spirale d'Ulam n'est pas obligatoirement définie pour commencer avec le chiffre 1).
Syracuse / Langton / Ulam; peut-on parler de schémas similaires ?
Comment ces problèmes complexes sont abordés et les retrouvent-on dans la "vrai vie" en tant que phénomènes physiques?
-----

[Deedee81]

Salut,

Dit, tu as l'habitude maintenant, tu ne devrait plus oublier de dire bonjour !!!!

Comment ces problèmes complexes sont abordés

Difficilement

Au début on tente des approches algébriques, on fait diverses simulations pour comprendre.... Puis quand ça résiste, on finit rapidement par avoir secoué le cocotier dans tous les sens et il faut passer à des outils autrement plus sophistiqués. Un exemple bien connu est la démonstration du théorème de Fermat par Wiles https://fr.wikipedia.org/wiki/Dernie...%A9monstration
Rien que des trucs comme courbes elliptiques et les fonctions modulaires, c'est pas de la petite bière.

Par exemple, il est même démontré (je ne sais pas comment) qu'il est impossible de résoudre ce bon vieux P=NP par des méthodes simples de type algébrique. Mais ça ne me surprend guère, quand des milliers de gens s'attaquent au même problème, s'il y avait une solution simple, elle aurait été trouvée (bon, ça, ça ne constitue pas une démonstration of course. Mais ça parait évident. A noter qu'une méthode de type Ulam n'est pas simple mais extrêmement simpliste).

Tiens, à ce propos, Terence Tao a fait une avancée récente (mais loin d'être définitive) sur Syracuse :
https://www.larecherche.fr/math%C3%A...8s-de-syracuse

J'ai trouvé l'article :
https://arxiv.org/abs/1909.03562

J'ai jeté un oeil. Si je devais le décortiquer, je suerais sang et haut. C'est du haut vol.

Syracuse / Langton / Ulam; peut-on parler de schémas similaires ?

Trèèèèèèèèèèèès superficiellement.

et les retrouvent-on dans la "vrai vie" en tant que phénomènes physiques?

Non, pas à ma connaissance.

En théorie des nombres il n'est pas rare qu'un problème n'ait qu'un intérêt marginal en soi. Mais son analyse est utile en soi aussi. Par exemple, pour le théorème de Fermat, l'utilité de la démonstration est surtout les outils que Willes a développé et qui ont permis de progresser dans le programme de Langlands : https://fr.wikipedia.org/wiki/Programme_de_Langlands

Tiens, et tu as déjà vu cette page ?
https://fr.wikipedia.org/wiki/Cat%C3...n_r%C3%A9solue

Y a du boulot

Il en manque : la conjecture des nombres parfaits impairs https://fr.wikipedia.org/wiki/Nombre...parfait_impair. Je m'y étais attaqué étant gamin (quinze ans) .... en essayant des méthodes analogues à celle des nombres parfaits pairs (aaaah naïveté quand tu nous tiens, mais , héééé, je n'avais que quinze ans). Mais ce fut quand même instructif pour moi car j'ai vite vu les difficultés rencontrées et comme on dit, c'est en tombant qu'on apprend à se relever

[Deedee81]

Ah tiens, il y a forcément des conjectures abordables.

J'en avais vu une dans la théories des algèbres (DES algèbres, pas DE l'algèbre), plus exactement les algèbres de von Neuman.
Je ne m'en souviens plus de tête, j'ai ça chez moi, mais en gros il y avait à un moment donné une méthode de construction d'algèbres et une remarque à propos de deux algèbres ainsi construites et où l'auteur disait qu'on ignorait si ces deux algèbres étaient identiques ou pas.

Ce type de problème est en réalité de peu d'intérêt et assez spécialisé.... donc fort peu de gens ont dû creuser la question. De plus, superficiellement, il ne semble pas des plus monstrueux (mais ça peut être trompeur). Donc il y a une bonne chance de démontrer le résultat sans devoir s'enfermer des années pour y arriver comme avait fait Wiles Faut juste bien maîtriser le domaine concerné (ce qui n'est pas tout à fait mon cas, je suis plutôt à 50% dans ce domaine) et se retrousser les manches.

Mais bon, arriver à démontrer ça a un côté satisfaisant mais pas très utile ni glorieux. Même pas de quoi en faire une thèse. Mais pour celui qui veut se faire les dents sur des problèmes non résolus pas trop dingues... ce genre de conjecture est utile. Et il suffit souvent de se référer à ses lectures mathématiques préférées, on en trouve un peu partout

[Deedee81]

Et il suffit souvent de se référer à ses lectures mathématiques préférées, on en trouve un peu partout

Un exemple : De Lahaye dans PLS a sa rubrique mathématique. Il présente tous les mois des sujets vraiment intéressants. Et soulève constamment diverses conjectures. Et bien, plus d'une fois, il a signalé que des progrès avaient été fait grâce à des lecteurs. (EDIT à la fin de sa rubrique, souvent un truc du genre Monsieur Untel de ... a démontré que ...)

Les pépipes se trouvent partout. Faut juste creuser

[A voir en vidéo sur Futura]

[invite84127968]

Désolé de mon empressement d'hier... donc Bonjour avec n-1 jour et +1 pour aujourd'hui

Effectivement il y a pléthore de conjectures et les outils de résolution pas à la portée du premier venu. La nature de cette complexité est certainement variée mais j'imagine qu'il y a peut-être des typologies, des voisinages qui font aborder ces problèmes en utilisant des outils de nature semblable.
Si on réduit l'outillage au plus simple pour n conjectures il doit rester un minimum d'opérandes toujours commun peut-être? (je tente d'étudier les structures algébriques en ce moment) et si l'on est obligé d'utiliser un outil différent entre deux conjectures à partir d'un certain stade pour les démontrer on pourrait peut-être envisager une catégorisation, des familles? Dans l'idée est-il possible d'envisager un opérande imaginaire pour classer les conjectures non démontrées si tant est qu'un tel classement est envisageable?

[Médiat]

Ce que vous demandez nécessiterais de savoir comment telle ou telle conjecture sera résolue ; on peut, au mieux, considérer les axes actuels de recherche.

Il n'est pas interdit de penser que Fermat avait vraiment une démonstration de son grand théorème, elle n'aurait rien à voir avec celle de Wilkes, on n'est jamais à l'abri d'un Ahah comme aurait pu dire Martin Gardner

[invite84127968]

Bonjour, Martin Garder est un auteur à lire de ce que je viens de lire sur wikipedia..
Toute cette problématique me rappelle les discussion que l'on avait entre joueurs d’échecs dans les années 90 (j'étais un très modeste mais j'avais la chance de côtoyer parmi les premiers GMI Français). A cette époque j'avais cette question "existe t-il un premier coup toujours gagnant?" en surfant sur les liens que renvoie la page sur Martin Garder, je me retrouve dans ce même univers.. c'est rafraichissant

[Deedee81]

Salut,

j'imagine qu'il y a peut-être des typologies, des voisinages qui font aborder ces problèmes en utilisant des outils de nature semblable.

C'est souvent ce qu'il y a le plus intéressant dans les conjectures. C'est trouver les "ponts" entre différentes questions voire domaines à l'aide d'outils variés. Et la chute d'une conjecture en entraine parfois d'autres.

Mais je suis de l'avis de Médiat. Il est amha quasiment impossible de deviner quels outils pourraient convenir pour résoudre une conjecture. Ce serait trop beau (certainement plus de la moitié d'un problème serait résolu si on savait ça). Ce n'est qu'en essayant qu'on peut savoir. L'exemple de la conjecture de Riemann est emblématique. Si beaucoup de progrès a été fait grâce aux outils de l'analyse spectrale, le fait est qu'on a essayé un peu tous les outils possibles de (presque) tous les domaines mathématiques. Et elle n'est toujours pas résolue et malgré des milliers de pages écrites sur le sujet, bien malin celui qui devinera quels outils permettront de trouver. Et en effet un Ahah est toujours possible. Là aussi Fermat est emblématique : tout était mûr pour trouver et pourtant.... quant Wiles a annoncé sa réussite on est tous tombé sur le c.. (enfin, moi en tout cas).

A noté que le Ahah n'est pas réservé aux maths. Je suis sûr que lorsqu'on va (enfin) comprendre comment fonctionnent les supraconducteurs haute température il y aura un énorme Ahah (y en a déjà eut : hein !!!! Un supra avec du fer ???? Impossible ! Et pourtant....)

Un classement possible est celui des domaines du problème : théorie des nombres, analyse fonctionnelle, topologie générale, différentielle, algébrique, catégories, etc... etc....
Ca peut être intéressant car il y a forcément des domaines qu'on connait mieux que d'autres.

j'étais un très modeste mais j'avais la chance de côtoyer parmi les premiers GMI Français

J'ai eut l'occasion de jouer aux cotés de Bacrot à peu près à la même époque. (pas contre lui, près de lui, j'avais un niveau de faible joueur de club, enfin, pour un club de division deux qui lorgnait vers la un ).
Il était très jeune et j'avais été très impressionné. C'était amusant de le voir jouer en aveugle contre son père.

[invite84127968]

Bonjour,

en lisant l'histoire du grand théorème de FERMAT et prenant la perspective du travail de Martin Gardner « Mathematical Games » je trouve cette compréhension de l'univers mathématique:
une transposition d'un énoncé mathématique simple en écriture dans un cadre en premier lieu imagée puis située dans un ou plusieurs domaines d'approche révèle une complexité qui alors engendre la création d'outils mathématiques.
Le haha apparaitrait dans la formalisation en logique et l'intuition serait parfois de trouver la bonne projection d'une conjecture sur un plan imagé pour en faire un domaine: l’arithmétique de l'horloger devient l’arithmétique modulaire.
En créant des "jeux" mathématiques, qui sont peut-être assimilables à des situations ou des contextualisations mathématiques, il est généré potentiellement et de façon induite des règles, les trouver prouverait la réalité du jeu ?

[minushabens]

A cette époque j'avais cette question "existe t-il un premier coup toujours gagnant?"

pour la petite histoire, quand j'étais étudiant à Montpellier dans les années 80 j'ai un peu suivi les cours d'Alexandre Grothendieck. Il posait la même question: trouver un algorithme gagnant aux échecs (en d'autres termes résoudre le problème "les blancs jouent et gagnent" à partir de la position initiale). Il pensait que ce problème était hors de portée des mathématiques de l'époque. Mais ça n'est qu'une opinion, même si c'était celle de quelqu'un qui connaissait bien les mathématiques.

[invite84127968]

A l'époque je vivais en colocation, il y avait un GMI et un MI dans la coloc et gravitait autour évidement des personnes de l'univers mathématique universitaire.. on y a passé des heures de discussions, la discussion elle même était un moyen de perfectionner son jeu pour tout à chacun.
Les idées gravitaient autour de la réalité de l'égalité de départ et de son devenir en cours de partie, entre réalité ou illusion des avantages positionnels et matériels du fait des potentiels combinatoires etc... les coups "neutres", l'irréversibilité du mouvement des pions... L'analyse des parties était aussi au cœur de ce sujet pour savoir déterminer avec finesse le moment ou un des adversaires avait commis une "erreur". L'analyse des parties de Kasparov
contre deep blue en 97 avait été aussi l'occasion de bien des débats
Poser la question du trait gagnant du point de vue mathématique renvoie vers une combinaison de concepts qui ne peut-être établie si les univers conceptuels du jeu ne peuvent avoir de liens entre eux: la phrase est un poil lourde mais voilà ou j'en était resté pour ma part .

[invite84127968]

J'ai tenté de faire le tour de tout ce qui m'a été répondu dans ce fil.. j'ai fini sur la Théorie des représentations, les Algèbres associatives et la théorie des modules comme concepts à étudier au préalable.
Comme quoi j'ai du boulot pour comprendre mes propres questions

Au passage, égaré dans la théorie des jeux, je me suis promené sur le concept P=NP (lien bien fait je trouve: https://www.imj-prg.fr/fetes/FS2009/...chiers/PNP.pdf) et je suis au bout d'un moment tombé sur cet article : https://www.lamsade.dauphine.fr/~bonnet/publi/games.pdf on parle très brièvement des échecs dans ces deux liens.

[Tryss2]

pour la petite histoire, quand j'étais étudiant à Montpellier dans les années 80 j'ai un peu suivi les cours d'Alexandre Grothendieck. Il posait la même question: trouver un algorithme gagnant aux échecs (en d'autres termes résoudre le problème "les blancs jouent et gagnent" à partir de la position initiale). Il pensait que ce problème était hors de portée des mathématiques de l'époque. Mais ça n'est qu'une opinion, même si c'était celle de quelqu'un qui connaissait bien les mathématiques.

Mais un algorithme est trivial, vu que le nombre de parties possible est fini. La question c'est plutôt est-ce que l'on va arriver à trouver un algorithme qui réponde à la question en un temps raisonnable. Parce que fondamentalement, il n'y a pas de différence majeure entre le morpion et les échecs (ou le go)

[minushabens]

Mais un algorithme est trivial, vu que le nombre de parties possible est fini.

tu vas vexer les combinatoriciens, qui ont la faiblesse de s'intéresser à des problèmes finis mais ne les trouvent pas triviaux du tout...

[Tryss2]

Ce qui intéresse les combinatoriciens, c'est des solutions utilisables aux problèmes. Lister les configurations n'est en général pas une solution utilisable, même si c'est une solution.

[invite84127968]

Quand vous parlez de solutions utilisables, vous voulez dire réalistes d'un point de vue d'exprimer la solution en un temps compatible avec la réalité? J'entends là que le temps de calcul soit observable par celui qui lance le calcul (un être humain pourrait observer une solution dix générations après le début du calcul par exemple).
Aux échecs le problème est fini dès lors que l'on instaure la règle des 50 coups mais on a 10^6000 parties possibles..( y compris celles qui n'ont pas de sens): https://fr.wikipedia.org/wiki/Nombre_de_Shannon
Rmq: Sans la règle des 50 coups la nullité d'une partie est quand même établissable (final roi vs roi).

[Deedee81]

Salut,

pour la petite histoire, quand j'étais étudiant à Montpellier dans les années 80 j'ai un peu suivi les cours d'Alexandre Grothendieck. Il posait la même question: trouver un algorithme gagnant aux échecs (en d'autres termes résoudre le problème "les blancs jouent et gagnent" à partir de la position initiale). Il pensait que ce problème était hors de portée des mathématiques de l'époque. Mais ça n'est qu'une opinion, même si c'était celle de quelqu'un qui connaissait bien les mathématiques.

Pfffff, tout le monde sait bien qu'on a la solution. On avait posé la question à Bogoliubov. Il avait répondu :
"Quand j'ai les blanc je gagne parce que j'ai les blancs. Quand j'ai les noirs, je gagne parce que je m'appelle Bogoliubov"
(à prononcer avec l'accent russe)

Rmq: Sans la règle des 50 coups la nullité d'une partie est quand même établissable (final roi vs roi).

Heu, non, tu ne peux pas prouver ainsi l'inexistence de stratégie gagnante depuis la position initiale.
(même si je pense comme beaucoup que c'est nul, mais ce n'est qu'une opinion)

Pour info, on appelle cela "résoudre le jeu". Et presque tous les jeux ont été résolus grâce à des ordis : cherckers, dames anglaises, morpion ou go-moku, othello-réversi...

Mais quelques jeux résistent : échecs, go, shogi, etc...

[Deedee81]

Les jeux résolus :
https://fr.wikipedia.org/wiki/Jeu_r%C3%A9solu

[minushabens]

Ce qui intéresse les combinatoriciens, c'est des solutions utilisables aux problèmes.

bah oui, je suppose que l'idée était de trouver un algorithme utilisable, ce qui est d'ailleurs un peu implicite dans la notion d'algorithme.

[Tryss2]

Pourquoi? Le bogosort est bien un algorithme de tri, pourtant il est inutilisable en pratique

[minushabens]

je trouve que l'existence d'un algorithme gagnant aux échecs n'est pas si évidente. Il se pourrait que quelle que soit la stratégie des blancs les noirs arrivent à obtenir le nul.

[Deedee81]

Il se pourrait que quelle que soit la stratégie des blancs les noirs arrivent à obtenir le nul.

C'est indémontrable. Mais si on fait un sondage :
- la majorité pensent que le jeu est théoriquement nul.
- Une minorité pensent que l'avantage des blancs est suffisant pour gagner à coup sûr (avec la bonne stratégie)
- quelques isolés pensent que c'est noir qui devrait gagné (comme disait un joueur d'échec/auteur dont le nom m'échappe, d'un ton moqueur : "grâce aux vertus de la contre-attaque ?")

Bon, on a quelque peu dérivé là, désolé.

[invite84127968]

Rmq: Sans la règle des 50 coups la nullité d'une partie est quand même établissable (final roi vs roi).

Heu, non, tu ne peux pas prouver ainsi l'inexistence de stratégie gagnante depuis la position initiale.
(même si je pense comme beaucoup que c'est nul, mais ce n'est qu'une opinion)
Pour info, on appelle cela "résoudre le jeu". Et presque tous les jeux ont été résolus grâce à des ordis : cherckers, dames anglaises, morpion ou go-moku, othello-réversi...
Mais quelques jeux résistent : échecs, go, shogi, etc...

Bonjour je ne fait pas cette remarque dans ce sens au contraire je souligne que le distinguo avantage positionnel/avantage matériel est relatif. En fin de partie l'aboutissement gagnant est la présence déterminante (suffisant pour amener le MAT) d'un ou des deux avantages exploitable avec le trait.
L'ensemble des parties possibles génère un arbre décisionnel avec des moments de neutralité comparable au début de partie, si l'on calcul qu'il y a plus de parties gagnantes pour les blancs sur l’ensemble des variantes est-ce que cela établi une perte à coup sur des noirs?

[Deedee81]

Salut,

je ne fait pas cette remarque dans ce sens au contraire

J'avais mal compris. Enfin, ça valait sans doute la peine que je précise

si l'on calcul qu'il y a plus de parties gagnantes pour les blancs sur l’ensemble des variantes est-ce que cela établi une perte à coup sur des noirs?

Ca augmente les chances mais c'est largement insuffisant pour prouver (*) l'existence d'une stratégie gagnante (**).

(*) Pour que ça constitue une preuve il faudrait atteindre presque 100% de positions finales gagnantes !!!!
(**) Je ne connais pas de méthode simple pour prouver l'existence (ou non) d'une stratégie gagnante. Prouver l'existence d'une stratégie optimale (***), ça oui, c'est pas très difficile (c'est un théorème de Von Neumann (****)). Mais sa nature.... je ne connais pas d'autre méthode que la résolution du jeu, même pour des jeux très simples comme Tic Tac Toe.
Exceptions : l'existence de stratégies gagnantes qu'on peut décrire en quelques lignes. C'est le cas pour le jeu des allumettes et même le jeu de Nim (multipaquets) avec d'ailleurs un étrange algorithme (il faut additionner des nombres binaires comme s'ils étaient décimaux ).
A noter que la stratégie optimale (de valeur nulle) au tic tac toe peut se décrire, elle est pas trop mortelle, mais elle nécessite une bonne dizaines de lignes quand même.
Et la plupart des jeux résolus ont une stratégie optimale décrite.... par une base de données monstrueuse !!!!

(***) Dans les jeux non probabilistes à information parfaite. Mais sinon il existe parfois des stratégies dites mixtes.

(****) Le minimax. Qui est même la base du mécanisme d'analyse des programmes de jeu (sauf ceux à apprentissage profond of course).
J'ai programmé des tonnes de jeux avec ça (enfin, avec alpha-bêta + autres algorithmes) : tic tac toe, morpion, échecs, othello-réversi,...

[invite84127968]

C'est un espace de réflexions que je ne pensai pas aussi prolixe..
De ce que j'ai lu à travers les éléments décrits plus avant, la nature du jeu en général est l'obtention du gain à travers l'opposition (de concepts combinés: souvent une position, une configuration et une valeur matérielle ou autre) forcée (obligation de jouer pour constituer le tour et la continuité de la partie).
Une partie ou les deux adversaires ont un objectif divergeant (l'un veut gagner, l'autre perdre ou faire nul) est gagnante pour les deux joueurs si la nature du jeu le permet (echecs par exemple), et s'il y a convergence alors émerge la complexité à travers les propriétés du jeu.
La bataille (avec 2 joueurs) est une partie de carte dont l'issue est prédéterminée par la donne: on obtiens un avantage positionnel et matériel pré-établi
La suite de Syracuse ou une conjecture peuvent être classée dans un jeu type bataille, on positionne "11" (matériel et position sont confondus) et le "vol" qui en découle sera lié à la nature du jeu (n*(*3 si impaire / 2 si paire jusqu'à 1) mais il y a une nature complexe qui émerge quand même qui est le moment ou la suite Syracuse "croise" un élément de la suite a(n) = 4^n ou un élément d'une suite qui conduit à cette suite a(n) = 4^n qui lui même est amené par un autre..
Je ne sais pas si je décris bien les choses mais cette complexité pour identifié un "moment" déterminant dans la résolution me semble de même nature entre un jeu et certaines conjectures.

[invite84127968]

Pour illustrer mon dernier propos deux liens qui au final ne mènent qu'à la sensation conceptuelle sans la formaliser:

https://perso.liris.cnrs.fr/eric.duc...s/coursCGT.pdf
https://hal.archives-ouvertes.fr/hal-01593181/document

Il nous manque un truc c'est la seule conclusion que je puisse faire, dans l'état actuel avec ce doute sur la nature du truc.. Garcimore à l'aide!!