Une réponse à propos de Collatz
dans Shtam
@GaBuZoMeu
tu ne crois pas si bien dire....c'était d'ailleurs une de mes premières publications : une preuve que les généralisations du "3x+1 problem" forment un ensemble indécidable.
voici le rapport de recherche (fait en Master) qui a donné l'article (qui était paru dans TCS)
ah...par contre je vois que mon truc sur Goldbach a disparu......bouh...on m'explique pourquoi ?
tu ne crois pas si bien dire....c'était d'ailleurs une de mes premières publications : une preuve que les généralisations du "3x+1 problem" forment un ensemble indécidable.
voici le rapport de recherche (fait en Master) qui a donné l'article (qui était paru dans TCS)
ah...par contre je vois que mon truc sur Goldbach a disparu......bouh...on m'explique pourquoi ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
n'a rien d'autre que la fonction nulle partout comme solution si et seulement si la conjecture de Collatz est vraie.
alors....au boulot les amis fonctionnalistes ! ;-)
C'est paru ici :
Serge Burckel (1994), Functional equations associated with congruential functions,
Theoretical Computer Science123(1994), 397–406.
J'y donne aussi une équation fonctionnelle qui n'a que la solution triviale $R(z)=0$ si et seulement si la conjecture "3x+1" est vraie :
$$3z^3R(z^3)-3z^9R(z^6)-R(z^2)-R(\omega z^2)-R(\omega ^2z^2) = 0,$$ où $\omega= \exp({{2i\pi}\over{3}})$
ci-joint le rapport de recherche (c'est quasiment l'article). J'étais alors en DEA à Caen, élève de Patrick Dehornoy.
Soit la suite de Collatz composée des six termes impairs A, B, C, D, E, F. Si on calcule F à partir de
$B=\dfrac{3\,A+1}{a}\,;\,C=\dfrac{3\,B+1}{b}\,;\,D=\dfrac{3\,C+1}{c}\,;\,E=\dfrac{3\,D+1}{d}\,;\,F=\dfrac{3\,E+1}{e}$
où $a,b,c,d,e$ sont des puissances de 2, on obtient
$F=\dfrac{3^0}{e}+\dfrac{3^1}{d\,e}+\dfrac{3^2}{c\,d\,e}+\dfrac{3^3}{b\,c\,d\,e}+\dfrac{3^4\,(3\,A+1)}{a\,b\,c\,d\,e}$
Maintenant on simplifie la dernière fraction :
$B=\dfrac{3\,A+1}{a}\to\dfrac{3^4\,(3\,A+1)}{a\,b\,c\,d\,e}=\dfrac{3^4\,B}{b\,c\,d\,e}$
puis
$\dfrac{3^3}{b\,c\,d\,e}+\dfrac{3^4\,B}{b\,c\,d\,e}=\dfrac{3^3\,(3\,B+1)}{b\,c\,d\,e}$
On vient d'éliminer A. On répète cette simplification pour éliminer successivement B, C et D, c'est-à-dire jusqu'à ce qu'il ne reste plus que
$F=\dfrac{3\,E+1}{e}$
Cette opération de simplification à l'extrême fonctionne évidemment quelle que soit la longueur de la suite impaire (composée uniquement de ses termes impairs).
Si je te parle de ça c'est parce que j'ai parcouru une partie de ton blog et que j'ai vu que tu te posais des questions sur la nature de la Réalité. D'où ma question (de nature épistémologique) : étant donné qu'on peut réduire une suite de Collatz à son dernier terme, peut-on encore dire qu'une telle suite existe ?
Grande avancée qui devrait bien faire avancer la recherche.
<<on n'a pas vraiment avancé.>>
Pour la question "philosophique", elle se ramène à une expression du genre : est-ce que $vrai \implies vrai$ ?
Je pense que c'est vrai....à vérifier.
Une petite remarque à ce sujet : pour toutes propositions $P$ et $Q$, on aura toujours $P\implies Q$ ou $Q\implies P$ puisque
$$(\lnot P\vee Q)\vee(\lnot Q\vee P)$$
est une Tautology....C'est toujours vrai pour tous $P$ et $Q$
C'est donc vrai par exemple pour
$P$ : Dieu existe
$Q$ : L'Univers existe.
et même pour faire peur :
$P$ : La conjecture de Collatz est fausse
$Q$ : La réalité n'est qu'une illusion.
On peut aussi prendre par exemple $P$=Axiome du Choix et $Q$=Hypothèse du Continu.
C'est moins philosophique que Tautologique...tout comme la logique à Toto ;-)
J'espère avoir été amical et non brutal.
Bien à vous @Wilfrid
cependant, la notation concise que vous employez est intéressante : $$
f(N)={{3N+1}\over{n}}
$$ en supposant que les majuscules sont des nombres impairs et les minuscules des puissances de $2$ avec une relation entre $N$ et $n$ :
Alors, toute approche généralisable est vaine. C'est "pointu"...et c'est prouvé par codage des machines de Turing.
Je l'avais démontré....et donc du coup, j'avais aussi laissé tomber l'idée de résoudre ce problème un jour.
Ce n'est pas pour vous décourager mais pour vous donner du temps à consacrer à autre chose.
Et puis, entre nous, ce truc ne sert absolument à rien....juste à passer le temps.
Et même à perdre son temps....mais chut ! il faut pas trop le dire...(secret)
Il y a plein d'autres moyens plus intéressants pour passer son temps.
Ce machin, c'est juste un casse tête...limite un casse pipe.
Je préfère encore faire un SUDOKU.
Bien à vous,
serge
Des tas de choses qui apparemment ne servent à rien peuvent déboucher sur des découvertes inattendues. L'histoire des sciences regorge d'exemples de ce type.
Plus prosaïquement, je dirais que la réduction algébrique d'une suite de Collatz est en lien avec le fait qu'elle peut débuter par n'importe quel terme appartenant à la suite de départ. Si B est fonction de A alors la suite peut aussi bien débuter par B que par A, et si C est fonction de B alors elle peut débuter par C. Les termes suivants n'en seront pas altérés. Autrement dit, si la suite de départ est A, B, C, D, E, F, l'existence des termes A, B, C et D est accessoire.
D'autre part, il ne faut pas considérer F comme étant l'équivalent du 1 final. C'est seulement le successeur de E, quelle que soit la position de celui-ci dans la suite.
je ne vous connais pas...pourriez-vous commencer par me dire votre âge afin que je puisse adapter ma réponse ?
Merci
j'avais vu 8 ans tout à l'heure...là tu passes à 11 ans en quelques heures...Tu grandis vite dis donc :-)
De plus l'auto-dérision que tu utilises est un signe de maturité. Bravo !
Pour tes questions sur la conjecture, on comprend mieux. On comprend aussi que tu es un passionné des maths et tes messages en sont d'autant plus respectables.
Ceci dit, je dois d'autant plus te conseiller de ne pas trop te fixer sur cette saleté de conjecture ! Tu peux t'amuser à faire quelques calculs et en profiter pour apprendre d'autres choses...mais vraiment, on n'arrivera pas à la prouver comme ça. Et personne ne sait vraiment comment. Les mathématiques n'ont pas encore les outils pour résoudre ce problème. Alors apprends tranquillement les mathématiques, comme un élève de musique apprend le solfège, et quand tu maitriseras ce solfège, tu pourras composer de beaux morceaux de mathématique qui te feront plaisir et qui permettront même peut-être de répondre à des questions....comme par exemple pour ce fichu problème. Pour l'instant, amuse toi avec des petites énigmes...celles qui ont des solutions et cherche par toi même et si tu ne trouves pas, ce n'est vraiment pas grave puisque cela te donnera l'occasion d'apprendre quelque chose de nouveau et de progresser dans ta sensibilité.
Bien à toi,
serge
Il y a néanmoins une contradiction dans tes propos : tu cites Paul Erdös ("Les mathématiques ne sont pas encore prêtes pour la résolution des problèmes de type 3n+1"), et par ailleurs tu affirmes que tes conclusions en la matière sont définitives et sans appel, allant jusqu'à critiquer sévèrement une réflexion dont l'objet est d'acquérir (avec un peu de chance) une vision différente du problème. Parce que c'est bien de ça dont il s'agit : "qu'est-ce qui, dans notre approche de Syracuse, pose problème au point qu'on soit incapables d'y comprendre quoi que ce soit ?".
Je ne suis pas certain, contrairement à ce que je déclarais dans mon premier post, que tu sois l'auteur des articles apparaissant dans le blog "Sigle/Signe" (tu en donneras l'adresse si tu veux), d'autant plus qu'ils ne sont pas signés. Mais si c'est le cas, force est de reconnaître que ce que tu déclares dans l'article "I.A. Idiotie Artificielle" fait de toi un contestataire de la pensée dominante (et je partage d'ailleurs tes conclusions) – ou une personne disposée à contester le paradigme actuel. Mais il est vrai que la contestation ne porte pas seulement sur l'IA, elle concerne également l'espace-temps, le big bang, l'expansion de l'univers, etc., etc. Tout est contestable, toute théorie peut être invalidée à tout moment.
Donc, comment quelqu'un se trouvant dans cet état d'esprit peut-il affirmer que ses conclusions en matière de conjecture de Collatz ne sauraient être remises en cause ?
je suis pourtant bien l'auteur de tout ce qui se trouve sur le site www.sigle.space
je n'affirme rien de particulier concernant cette conjecture si ce n'est une équivalence en termes d'équations fonctionnelles et qu'elle et ses généralisations forment un ensemble indécidable. Je l'affirme parce que j'en ai fait la preuve formelle.
Le corollaire de ceci c'est qu'une éventuelle preuve de la conjecture de Syracuse ne peut pas être uniformément généralisable à l'ensemble des questions du même style. Tout comme il n'existe pas de méthode automatique pour prouver des théorèmes dans l'arithmétique de Peano. Là, c'est encore plus précis car cela ne concerne que les questions de ce type défini par des congruences.
Si tu es intéressé,par ces question, tu peux lire le livre :
Gödel, Escher, Bach : Les Brins d'une Guirlande Éternelle de Douglas Hofstadter
Je crois même qu'une version PDF est disponible en ligne, mais le livre en soit est un beau cadeau à te faire pour Noël.
Bien à toi,
serge
Par contre on peut télécharger gratuitement chez Dunod le PDF de 30 pages "Je suis une boucle étrange", en français, dans lequel D. Hofstadter évoque la démarche intellectuelle qui l'a conduit à écrire "Gödel, Escher, Bach". Cette lecture donne le ton, en quelque sorte.
C'est bien d'avoir cherché. Je pense que ce serait bien que tu l'aies. Il parle de maths, de musique, de dessins, de logique, d'informatique avec des petites histoires sympathiques et de belles illustrations. Je me demande même s'il n'y parle pas de la conjecture de Syracuse à un moment...
Tu dois pouvoir le trouver dans une bonne bibliothèque près de chez toi...ou alors le livre en occasion à environ 30 euros
ou neuf à 50 euros.
Je t'aurais bien envoyé mon exemplaire...cependant je l'ai prêté au fils d'une amie...il a 14 ans.
Bien à toi
et pour apporter une petite touche d'humour :
si comme tu dis, ton psychologue évalue ton QI à 45, il est peut-être un excellent psychologue mais également un piètre calculateur. Ce n'est pas incompatible.
;-)
J'ai parcouru en diagonale la version PDF anglaise. Je cherchais ce que Hofstadter disait sur l'Intelligence Artificielle, sachant que cette version est sortie en 1979 (1985 pour la traduction française) et qu'à l'époque ce vocable pouvait difficilement faire référence à autre chose qu'aux travaux d'Alan Turing ("Computing machinery and intelligence", publié en 1950) et à leurs développements par d'autres chercheurs. Et j'ai trouvé un passage plutôt significatif : "Il apparaît clairement que durant les prochaines décennies des progrès substantiels seront faits dans l'élucidation de ce qu'est l'intelligence humaine. Il se peut en particulier que des spécialistes de la psychologie cognitive, des chercheurs en Intelligence Artificielle et des neuroscientifiques soient capables de synthétiser le savoir qu'ils auront acquis et parviennent à une définition de l'intelligence".
En 40 ans ce n'est jamais arrivé. Aujourd'hui encore un nombre infime de gens - qui ne comprend pas les spécialistes cités hormis les plus progressistes d'entre eux - est capable de donner de l'intelligence une définition qui tienne debout. Et c'est sur cette ignorance que repose tout l'argumentaire publicitaire autour de ce qu'on nomme l'IA, qui de mon point de vue n'est qu'une fabrique à rêve dont l'unique objectif est de vendre des appareils dits "intelligents" mais qui en réalité le sont infiniment moins qu'une simple bactérie.
PDF : téléchargement à cette adresse. Les explications de Turing à propos des conditions de son test débutent page 16 ("Alan Turing : Les ordinateurs et l’intelligence") ; les objections contre les machines pensantes débutent au bas de la page 20 ("Vues contradictoires sur la question principale").
L'objection 2, celle de l'autruche, est toujours d'actualité : des tas de gens, dont Bill Gates, sont persuadés qu'en devenant conscientes les machines représenteraient un danger mortel pour notre espèce. Je trouve que ça en dit plus sur les personnes concernées que sur ce qu'il pourrait réellement advenir des machines.
Alan Turing avait été visionnaire sur un point : d'ici la fin du siècle, écrivait-il, les mentalités auront changé au point que l'idée de machines pensantes sera acceptée sans objection. Depuis plus d'une décennie, en effet, l'idée que les machines puissent penser (être intelligentes) semble faire consensus. Pourquoi ? J'y vois personnellement l'efficacité du matraquage médiatique et publicitaire autour de l'IA, qui apparemment a pour effet d’annihiler toute réflexion. On peut même situer le début de ce changement de paradigme avec précision : 2007, la sortie du premier iPhone, ou smartphone (littéralement "téléphone intelligent"). A force de passer leur temps libre plongés dans leur écran et de constater à quel vitesse le savoir-faire de ces appareils évolue, les milliards d'utilisateurs ont fini par accepter l'idée que ceux-ci sont réellement intelligents, surtout qu'ils apprennent de leurs habitudes et se plient à leurs préférences avec toujours plus de pertinence et d'efficacité.
Si Alan Turing dressait aujourd'hui la liste des objections contre l'idée de machines pensantes, combien en trouverait-il ? Je sais d'expérience qu'il y en aurait très peu, voire aucune, surtout depuis l'introduction du concept selon lequel la conscience naitrait de la complexité d'un système, et chacun pense au cerveau mais aussi aux réseaux neuronaux artificiels, qui feraient paraît-il d'excellents candidats.
Une intelligence artificielle c'est un programme de moins de 10000 lignes, connecté à un corps et des sens (une voiture autonome ça peut convenir, une connexion internet aussi), tu le laisses tourner pendant très longtemps, et paf, il a appris tout seul à faire ce qu'un être vivant arrive à faire avec ses membres, son corps, marcher, voir, s'alimenter, butiner des fleurs.. On a le droit de lui donner quelques indices sur les objectifs (l'abeille c'est encodé dans son ADN qu'il faut se nourrir) mais pas de définir leur modalité précise (l'abeille n'est pas préprogrammée, dans son ADN, pour faire tout ce qu'elle fait, quels gestes faire exactement dans toutes les situations possibles).
Je n'ai pas trop le temps de suivre cette conversation pour l'instant.
Cependant, voici rapidement mon point de vue en quelques points.
Je pense qu'il n'y a pas une forme d'intelligence mais diverses formes. Elles peuvent ainsi se compléter par coopération.
Par exemple, se servir d'une petite RAM de quelques kilos peut nous aider bien que cette RAM ne soit pas intelligente.
Je suis d'accord avec @Wilfrid sur la plupart des points. Notamment, l'intelligence artificielle se base sur l'apprentissage et donc l'adaptation à des situations données, ne tolérant que quelques petites "perturbations". Mais, l'intelligence c'est justement de pouvoir aborder une situation de rupture avec le connu, comme s'adapter dans une situation nouvelle, devant un problème nouveau, confronté à une langue inconnue, etc...
Cette flexibilité de l'intelligence sera difficile à acquérir pour des machines.
L'intelligence peut ainsi être relative ou absolue. Certes, une intelligence relative peut suffire la plupart du temps. Mais elle sera débordée et totalement inefficace si elle est confrontée à des données inconnues. C'est aussi pourquoi, je trouve que les tests de QI ne sont pas valables pour mesurer ce caractère absolu et flexible d'une véritable intelligence. On peut tous nous exercer à faire, et réussir à la longue, les petites énigmes logiques ou de compréhension de ces tests. Même une machine devrait pouvoir le faire dans très peu de temps. Tout est relatif.
Pour finir avec une anti-thèse, j'ai aussi l'impression que l'on retrouve avec les machines la situation qui nous a conduit à définir l'intelligence à partir de conditions de sorte que seule l'espèce humaine en soit pourvue parmi les autres animaux. L'expérience nous a ensuite conduit à admettre que d'autres animaux sont intelligents d'après cette définition. A-t-on pour autant rehaussé le niveau des conditions ? Non. Je pense que le débat sera similaire pour l'IA.
L'essentiel est que l'intelligence relative des machines ne fasse pas perdre aux humains leur capacité à développer une intelligence absolue. C'est là que se situe le risque majeur. Dans mes dernières années d'enseignement j'ai entendu des étudiants de Master me dire : <<mais monsieur, cet exercice n'est même pas sur Google ! >>
Si on te pique avec une aiguille tu vas t'écarter et pousser un cri, preuve que tu es conscient. Cette preuve n'est aucunement liée à la valeur de ton QI. La seule situation dans laquelle tu ne réagis pas est lorsque tu dors d'un sommeil profond ou que tu es sous anesthésie générale : dans les deux cas tu es inconscient, et quelqu'un qui ne te connait pas n'a aucun moyen de savoir quel est ton degré d'intelligence.
Si on pique un smartphone il ne réagira d'aucune manière, preuve qu'il est inconscient. Pour qu'il donne l'illusion d'être conscient il faudrait l'équiper de "capteurs de piqure" et le programmer pour qu'il réagisse d'une manière quelconque. Un objet manufacturé étant inconscient, il n'y a strictement aucune possibilité qu'il soit ou puisse devenir intelligent. Là encore, on peut lui donner l'apparence d'être intelligent par programmation, mais les algorithmes les plus sophistiqués et les plus puissants ne pourront jamais le rendre conscient.
Le point commun entre une brute épaisse et un génie, que de toute évidence le degré d'intelligence sépare, est la conscience. La difficulté à définir ce qu'est l'intelligence tient justement dans ce point commun : comment deux individus apparemment aussi conscients l'un que l'autre peuvent-ils être, l'un une brute épaisse et l'autre un génie ? La seule explication est qu'il existe une gradation de la conscience : le génie serait dans un état de conscience supérieur à celui de la brute épaisse.
Considérons maintenant deux informaticiens à qui on demande d'animer un robot humanoïde en sorte de lui donner l'apparence de se comporter comme un humain. Si l'un des informaticiens est une brute épaisse et que l'autre est un génie, il semblera évident à tout le monde qu'une fois leur travail terminé les deux robots ne se comporteront pas d'une manière qu'on pourra qualifier d'aussi intelligente dans les deux cas !
La réponse à la question de savoir si une machine peut devenir intelligente est définitivement non, puisqu'elle n'est pas consciente et qu'il est impossible de faire en sorte que ça change. Elle peut seulement donner l'illusion de l'être, mais son intelligence apparente sera le reflet de celle de son programmeur. En d'autres termes, on ne pourra jamais séparer la créature de son créateur, on ne pourra jamais la rendre autonome.
Quant à savoir si une machine pourra un jour penser, la réponse est encore non, pour la même raison : penser requiert l'existence d'une entité consciente, le penseur.
En substituant simplement le mot conscience au mot intelligence on comprend mieux pourquoi l'idée de machines pensantes, intelligentes et autonomes est une utopie complète.
L'intelligence, c'est la chose la mieux répartie chez les hommes parce que, quoiqu'il en soit pourvu,
il a toujours l'impression d'en avoir assez, vu que c'est avec ça qu'il juge.
R.Descartes
Cordialement,
Rescassol
Dans ce contexte, "homme"="être humain".
Cordialement,
Rescassol
PS: rester
qui apprécie les ensembles et cette conjecture, voici une petite version ensembliste de cette question.
On part d'un multi-ensemble $S$ quelconque d'entiers (les éléments peuvent avoir plusieurs occurrences).
On définit une opération sur ces multi-ensembles de la manière suivante :
a). Pour tout élément $n$ de S, on rajoute $n+1$ à $S$ ainsi qu'une copie du plus petit élément $m$ de $S$.
b). Tant qu'il existe un doublon $(n,n)$ dans $S$, on le remplace par $(n+1)$
La conjecture revient à dire que la répétition de ces opérations conduit toujours à un singleton $S=\{m\}$.
Notez que dans ce cas, l'opération donnera $\{m,m+1,m\}$ qui devient encore un singleton $\{m+2\}$.
L'astuce pour le comprendre est de voir les éléments de $S$ comme les exposants d'une décomposition en base $2$ d'un nombre $N$. Cette astuce permet aussi de pouvoir "oublier" la division par des puissances de $2$ après avoir fait $3N+1$ car dans cette vision ensembliste, les nombres sont identifiés à décalages près. Ainsi $N,2N,4N,8N...$ sont dans la même classe d'équivalence. Par exemple $27$ se représente par
$\{0,1,3,4\}$ puisque $27=2^0+2^1+2^3+2^4$. Mais cela ne fait aucune différence de le représenter par $\{40,41,43,44\}$ ou encore par $\{40,40,40,43,43,43\}$ ou par $\{789,789,789,791,791,791,791,791,791\}$ etc....
Ainsi, l'opération en b) est presque inutile : elle ne change pas la classe du multi-ensemble. Elle ne sert que d'interface "humaine" pour nous aider à trouver le nouveau minimum et à pouvoir vérifier la présence d'un singleton dans cette classe....càd, si elle correspond à la classe de $1$.
Notez que l'on peut remplacer les éléments de ces $S$ par d'autres choses que des entiers...des ordinaux par exemple...du moment qu'il y a une notion de successeur comme $s(n)=n+1$ et de minimum. On arrive ainsi à une version du problème qui rappelle étrangement le théorème de Goodstein....non ?
https://fr.wikipedia.org/wiki/Théorème_de_Goodstein
Voici justement la suite des opérations à partir de ce fameux $27$ (j'indique les multi-ensembles et l'indice $N$ de leur classe)
On a $S$ puis
$S\cup S^+\cup\{m\}$ où $S^+$ est l'ensemble $\{n+1:n\in S\}$ et $m$ est le minimum de $S$ puis
le réduit de ce multi-ensemble par l'opération b)
[0, 1, 3, 4], 27
[0, 1, 3, 4, 1, 2, 4, 5, 0], 41
[6, 1, 4], 41
[6, 1, 4, 7, 2, 5, 1], 31
[6, 3, 4, 7, 5], 31
[6, 3, 4, 7, 5, 7, 4, 5, 8, 6, 3], 47
[9, 6, 7, 4, 5], 47
[9, 6, 7, 4, 5, 10, 7, 8, 5, 6, 4], 71
[11, 6, 7, 5], 71
[11, 6, 7, 5, 12, 7, 8, 6, 5], 107
[11, 9, 6, 12, 7], 107
[11, 9, 6, 12, 7, 12, 10, 7, 13, 8, 6], 161
[14, 12, 7], 161
[14, 12, 7, 15, 13, 8, 7], 121
[14, 12, 9, 15, 13], 121
[14, 12, 9, 15, 13, 15, 13, 10, 16, 14, 9], 91
[17, 12, 11, 14, 15], 91
[17, 12, 11, 14, 15, 18, 13, 12, 15, 16, 11], 137
[19, 12, 15], 137
[19, 12, 15, 20, 13, 16, 12], 103
[19, 14, 15, 20, 16], 103
[19, 14, 15, 20, 16, 20, 15, 16, 21, 17, 14], 155
[19, 18, 22, 15, 16], 155
[19, 18, 22, 15, 16, 20, 19, 23, 16, 17, 15], 233
[21, 19, 22, 23, 16], 233
[21, 19, 22, 23, 16, 22, 20, 23, 24, 17, 16], 175
[21, 19, 25, 18, 20, 23], 175
[21, 19, 25, 18, 20, 23, 22, 20, 26, 19, 21, 24, 18], 263
[27, 21, 19, 20], 263
[27, 21, 19, 20, 28, 22, 20, 21, 19], 395
[27, 23, 21, 28, 20], 395
[27, 23, 21, 28, 20, 28, 24, 22, 29, 21, 20], 593
[27, 25, 30, 21], 593
[27, 25, 30, 21, 28, 26, 31, 22, 21], 445
[27, 25, 30, 23, 28, 26, 31], 445
[27, 25, 30, 23, 28, 26, 31, 28, 26, 31, 24, 29, 27, 32, 23], 167
[33, 27, 28, 26, 31], 167
[33, 27, 28, 26, 31, 34, 28, 29, 27, 32, 26], 251
[33, 30, 27, 31, 34, 28, 32], 251
[33, 30, 27, 31, 34, 28, 32, 34, 31, 28, 32, 35, 29, 33, 27], 377
[36, 33, 34, 31, 28, 32], 377
[36, 33, 34, 31, 28, 32, 37, 34, 35, 32, 29, 33, 28], 283
[38, 31, 30, 33, 34], 283
[38, 31, 30, 33, 34, 39, 32, 31, 34, 35, 30], 425
[38, 36, 31, 39, 34], 425
[38, 36, 31, 39, 34, 39, 37, 32, 40, 35, 31], 319
[38, 36, 33, 41, 34, 37, 35], 319
[38, 36, 33, 41, 34, 37, 35, 39, 37, 34, 42, 35, 38, 36, 33], 479
[40, 38, 36, 41, 37, 34, 42, 35], 479
[40, 38, 36, 41, 37, 34, 42, 35, 41, 39, 37, 42, 38, 35, 43, 36, 34], 719
[44, 38, 36, 41, 37, 42, 35], 719
[44, 38, 36, 41, 37, 42, 35, 45, 39, 37, 42, 38, 43, 36, 35], 1079
[46, 40, 38, 41, 36, 37], 1079
[46, 40, 38, 41, 36, 37, 47, 41, 39, 42, 37, 38, 36], 1619
[46, 43, 38, 47, 41, 37], 1619
[46, 43, 38, 47, 41, 37, 47, 44, 39, 48, 42, 38, 37], 2429
[46, 43, 40, 49, 41, 38, 44, 42], 2429
[46, 43, 40, 49, 41, 38, 44, 42, 47, 44, 41, 50, 42, 39, 45, 43, 38], 911
[48, 41, 49, 43, 44, 50, 42], 911
[48, 41, 49, 43, 44, 50, 42, 49, 42, 50, 44, 45, 51, 43, 41], 1367
[48, 46, 52, 42, 50, 44, 43], 1367
[48, 46, 52, 42, 50, 44, 43, 49, 47, 53, 43, 51, 45, 44, 42], 2051
[54, 43, 44], 2051
[54, 43, 44, 55, 44, 45, 43], 3077
[54, 46, 55, 44], 3077
[54, 46, 55, 44, 55, 47, 56, 45, 44], 577
[54, 48, 57], 577
[54, 48, 57, 55, 49, 58, 48], 433
[54, 50, 57, 55, 58], 433
[54, 50, 57, 55, 58, 55, 51, 58, 56, 59, 50], 325
[54, 52, 60, 58], 325
[54, 52, 60, 58, 55, 53, 61, 59, 52], 61
[56, 60, 58, 61, 59], 61
[56, 60, 58, 61, 59, 57, 61, 59, 62, 60, 56], 23
[63, 61, 59, 60], 23
[63, 61, 59, 60, 64, 62, 60, 61, 59], 35
[65, 61, 60], 35
[65, 61, 60, 66, 62, 61, 60], 53
[65, 63, 61, 66], 53
[65, 63, 61, 66, 66, 64, 62, 67, 61], 5
[68, 66], 5
[68, 66, 69, 67, 66], 1
[70], 1
Je pensais qu'on en avait terminé avec les suites de Collatz ! N'est-ce pas ce que tu t'es échiné à faire comprendre ?
Il faudrait vraiment que tu regardes la définition d'ensemble indécidable ou au moins le livre dont je t'ai parlé.
En gros, un ensemble indécidable est un ensemble $S$ tel qu'il n'existe pas d'algorithme qui permette de dire à partir d'une donnée $x$ si $x\in S$.
Par exemple, l'ensemble des énoncés vrais qui parlent d'arithmétique est indécidable (Gödel).
Mais ce n'est pas parce que l'énoncé "$\exists x$ tel que $x=5$" fait partie de cet ensemble qu'il n'en est pas pour autant "indémontrable".
Simplement, il n'existera pas de méthode uniforme (ou si tu préfères, d'algorithme) pour faire ces preuves.
Ainsi, quand je dis que les généralisations de Syracuse forment un ensemble indécidable, c'est plus précis que cela. Cela restreint le théorème de Gödel à cette sous-classe très particulière. Mais encore une fois, cela n'interdit pas d'en obtenir une preuve. Simplement, cette preuve ne pourra pas être généralisable et sera très très très spécifique au problème.
Voilà....bien à toi
serge
On peut tout autant faire l'opération $S\longrightarrow S\cup S^-\cup\{m\}$ où $S^-=\{n-1:n\in S\}$ et $m$ est cette fois le maximum de $S$ et faire ensuite $(n,n)\longrightarrow n-1$.
Disons que les propriétés algébriques restent identiques....c'est juste pour dire que c'est structurel comme question et qu'elle peut s'extraire de l'arithmétique de Peano....encore à la "mode Goodstein".
Ça me fait penser à l'IA ;-). Il existe une classe de problèmes pour la résolution desquels aucun algorithme ne peut être mis en oeuvre. L'IA permet justement d'en résoudre certains. Le plus connu est certainement celui des photos qu'on soumet à une machine en lui demandant de sélectionner celles qui contiennent un chat. Après la phase d'apprentissage au cours de laquelle on soumet à la machine des milliers de photos de chats, ce qui prend beaucoup de temps parce qu'il faut procéder à de nombreux réglages, elle doit être en mesure de reconnaître les chats sur 100 % des photos qui en contiennent. Il n'existe aucun algorithme qui permettrait d'obtenir ce résultat.
Il y a une contradiction flagrante dans ce que tu viens de dire puisque les méthodes d'IA SONT des algorithmes. Rien de plus.
serge
En informatique l'idée de l'IA c'est essentiellement celle d'un algorithme, simple, qui génère du code. C'est hyper compliqué de générer du code (qui ne bug pas au bout de 3 instructions), donc c'est presque par définition : un algorithme qui sait générer du code est intelligent. Le problème c'est alors de discerner ce qui est du code et ce qui est des données, les réseaux de neurones (récurrents, ceux d'aujourd'hui ne le sont pas) et les trucs style jeu de la vie (auto-organisateur) sont très étranges sur ce point puisque ce n'est jamais clair si on parle de données ou de code.
Un petit correctif : dire qu'un problème seul est indécidable n'a aucun sens, du moins cela ne correspond pas à la notion de décidabilité.
Cette confusion est commise assez souvent, même dans des articles ou des livres.
En effet, je vais vous dire une trivialité : <<Tout ensemble fini EST décidable.>>
Pour le reste, en effet, $ZFC$ est une théorie incomplète. Tout comme Peano pour l'arithmétique.
Pour expliquer cela à ce cher @Wilfrid (et peut-être d'autres), pour tout algorithme $A$ qui énumèrerait les théorèmes d'arithmétique (énoncés bien formulés et vrais) en se basant sur une axiomatisation de celle-ci (comme celle de Peano) ou des méthodes ingénieuses ou d'IA etc...
il existera toujours une formule $G(A)$ qui est sémantiquement équivalente à "Je ne suis pas démontrable par ce cher algorithme $A$".
C'est une version algorithmique du résultat de Gödel.
Soit $G(A)$ est vraie et donc $A$ n'arrive pas à prouver quelque chose de vrai (incomplétude)
Soit $G(A)$ est fausse et donc $A$ prouve quelque chose de faux (inconsistance)
Ils le sont depuis 1982. Extrait de la page Wikipédia que je viens de citer : "En 1982, John Joseph Hopfield, physicien reconnu, donna un nouveau souffle au neuronal en publiant un article introduisant un nouveau modèle de réseau de neurones (complètement récurrent)."
Pourrais-tu préciser dans quelles circonstances on ne saurait pas distinguer le code des données ?
J'ai déjà suffisamment de mal avec les maths, alors si en plus je dois me plonger dans une problématique à la Gödel, non merci ! ;-)
J'ai l'impression que ta méthode revient à utiliser une variante (qui revient au même) de la suite de Collatz :
$u_{0}=a$ avec $a$ impair,
$u_{n+1}=(3u_{n}+1)/2^{v_{2}(3u_{n}+1)}$, où $v_{2}$ désigne la valuation 2-adique.
oui, c'est bien entendu. La suite pour $27$ c'était pour illustrer. Le point important de mon message concernait la "vision ensembliste" du problème et la possibilité de l'étendre à d'autres algèbres et en particulier à des ordinaux "à la Goodstein". Par ailleurs, ce codage permet d'oublier cette division par une puissance de $2$ et de manière générale d'oublier les nombres pairs.
Mais je suis d'accord avec toi que ce truc ressemble un peu aux suites de Goodstein au sens où, à mon avis, il doit en exister une démo dans ZFC (ou dans une théorie encore plus forte avec grands cardinaux et tutti quanti), mais pas dans Peano. Le danger est le même que pour Goodstein : si tu pars d'un $u_{0}$ impair mais non standard tu encours le risque que la suite se barre à l'infini.
Si je dis des conneries, n'hésitez pas à me corriger.
L'entier $27$ est égal à $2^0+2^1+2^3+2^4$. C'est codé par l'ensemble $\{0,1,3,4\}$.
Son image par la fonction de Syracuse est $3x27+1=82$ qui est $2^1+2^4+2^6$ codé par $\{1,4,6\}$.
Au lieu de diviser par $2$, on change d'unité. On dira que $2^1$ représente la nouvelle unité.
On considère donc les nombres à décalage près.
Ainsi la classe d'un nombre $N$ est obtenue par des décalages $2N,4N,8N,....$
Ainsi la classe de $27$ est codée par les ensembles de la forme : $\{m,m+1,m+3,m+4\}$.
Et la classe de $41$ est codée par les ensembles de la forme : $\{m,m+3,m+5\}$.
Quand on prend un entier impair $N$ et que l'on fait $3N+1$, c'est faire $N+2N+1$.
Maintenant, dans la suite de Syracuse, on peut laisser tomber la série de divisions par $2$ et faire l'opération suivante en considérant la plus petite puissance de $2$ d'un nombre comme si c'était la nouvelle unité. Cette nouvelle unité, c'est donc $2^m$ où $m$ est le minimum de l'ensemble.
Quand on regarde donc l'opération à une puissance de $2$ près, cela revient à ce que j'ai dit : on prend les éléments de $S$ (ce qui code $N$), on rajoute les successeurs (ce qui codera $2N$) et on rajoute encore le plus petit élément $m$ de $S$ (ce qui correspond à l'unité). Je répète qu'il faut voir cela à décalage près.
On obtient bien la transformation $S\longrightarrow S\cup S^+\cup\{min(S)\}$.
Ainsi l'image de n'importe quel ensemble de la classe de $N$ donnera un ensemble de la classe de $F(N)$ où $F$ est la fonction de Syracuse.
Sur l'exemple, $S_{27}=\{m,m+1,m+3,m+4\}$ devient $\{m,m+1,m+3,m+4\}\cup\{m+1,m+2,m+4,m+5\}\cup\{m\}$
qui correspond aussi, en faisant une série d'opérations $(n,n)\longrightarrow n+1$ :
$\{m,m,m+1,m+1,m+2,m+3,m+4,m+4,m+5\}$
$\{m+1,m+1,m+1,m+2,m+3,m+4,m+4,m+5\}$
$\{m+1,m+2,m+2,m+3,m+4,m+4,m+5\}$
$\{m+1,m+3,m+3,m+4,m+4,m+5\}$
$\{m+1,m+4,m+4,m+4,m+5\}$
$\{m+1,m+4,m+5,m+5\}$
$\{m+1,m+4,m+6\}$ càd un ensemble $S_{41}$ représentant la classe de $41,82,164,....$. Notez que tous les multi-ensembles précédents sont aussi des représentant de cette classe.
Remarque : cette série d'opérations n'est utile que pour trouver la nouvelle unité donnée par le minimum $m'$ et pour voir si on a obtenu un singleton.
On obtient ainsi le résultat suivant.
Proposition : La conjecture de Syracuse est vraie si et seulement si tout ensemble $S$ aboutit ultimement à un singleton.
Cette représentation des suites de Collatz est nettement plus élaborée que tout ce que j'ai pu voir jusqu'à présent, mais y a-t-il le moindre espoir de démontrer ta proposition ?
Si ton but est de la soumettre à la réflexion des membres de ce forum, ne crois-tu pas que tu aurais mieux fait de lui dédier un fil (dans un autre forum que Shtam je suppose) plutôt que de la noyer dans celui-ci, où peu la verront ?
c'est ma façon actuelle de fonctionner, tant pour les maths, la physique, la biologie, la politique, l'environnement, etc....
je sème de petites graines afin qu'elles germent si elles méritent de le faire.
Pour cette approche, comme je l'ai dit, c'est un préliminaire à une réalisation par des nombres ordinaux...ou plus.
J'y viendrai si j'ai un moment et des idées.
Mais je donne volontiers mes idées à qui en veut.
Une autre remarque. On peut tout aussi bien considérer la transformation : $$
S\longrightarrow S^-\cup S\cup\{\min(S)-1\}.
$$ C'est pareil, à translation près.
C'est louable, mais encore faut-il qu'elles soient visibles !
En même temps, si ta proposition n'est pas démontrable on revient à la case départ, non ?
Je m'intéresse depuis peu à la conjecture de Syracuse. Je suis tombé sur un article publié sur hal ( https://hal.archives-ouvertes.fr/hal-01574521/document ) d'un neuroscientifique qui prétend avoir démontré des théorèmes qui faciliteraient la démonstration de la conjecture de Collatz (en utilisant un arbre binaire des nombres entiers).
Les noms des théorèmes qu'il a démontrés sont assez exotiques.
Y aurait-il des spécialistes qui pourraient évaluer et faire une petite synthèse [de] la pertinence de cette publication (l'article en question n'est pas très long).
Merci d'avance aux âmes charitables
document
Sinon, je n'ai pas regardé les détails...mais cela semble tourner en rond avec des trivialités.
Pour en revenir aux ensembles, on pourra chercher une évaluation de ceux-ci dans à peu-près n'importe quelle algèbre.
Par exemple, la version "standard" de Syracuse donne l'évaluation avec des sommes de puissances de $2$.
Ainsi l'ensemble $\{0,1,3,4\}$ s'évalue par $2^0+2^1+2^3+2^4=27$.
Il en est de même pour $\{0,1,2,3,3,3,3\}$.
Mais on peut remplacer l'addition par une autre opération $\oplus$ et d'autres évaluations des éléments $i$ que par $2^i$.
Il suffit de considérer des suites d'éléments tes que $a_{n+1}=a_n\oplus a_n$.
Par exemple (et juste pour illustrer) on peut prendre $x \oplus y=x^y$ et la suite $a_0=x$ et $a_1=x^x$, $a_2={a_1}^{a_1}={x^x}^{x^x}$, etc.....
Ainsi $\{0,1,3,4\}$ s'évalue désormais par $a_0\oplus a_1\oplus a_3\oplus a_4$ :
$${{x^{x^x}}^{{{x^x}^{x^x}}^{{x^x}^{x^x}}}}^{{{{x^x}^{x^x}}^{{x^x}^{x^x}}}^{{{x^x}^{x^x}}^{{x^x}^{x^x}}}}$$
(....ça fait aussi de jolis dessins ;-)...)
Juste pour dire qu'il suffit de trouver une bonne réalisation et un bon-ordre $>$ tels que
$$val(S)>val(S')$$ où $S'$ est l'ensemble obtenu par l'opération. Je répète, on peut penser à des réalisations dans des ordinaux.....