Quasiment En fait ça peut même se prouver (c'est assez rigolo, la démonstration n'est pas très dure et tu peux la trouver, en anglais, dans un article publié il y a 86 ans. Spoiler : [Afficher le message] Article qui a d'ailleurs été à la base de quelque chose de beaucoup plus large que ce qu'il souhaitait prouver à la base )

@Migou : désolé, mais pas d'accord...

On pense que blablabla mais on ne sait pas le prouver

Peut-être n'a-t-on pas encore trouvé la bonne démonstration.
D'ailleurs tu avances un argument, et c'est marrant le chef pâtissier avance exactement l'inverse.

Et attention : prouver la convergence de manière automatisée ne veut pas forcément dire "parcourir toute la suite jusqu'à la fin". Une démonstration mathématique n'est qu'une succession d'étapes logiques et ça peut, formellement, être automatisé. Je n'ai pas besoin de parcourir toute la suite des 2^n pour savoir qu'elle ne converge pas. La preuve :

* Soit N un entier quelconque
* Soit E l'ensemble des entiers strictement supérieurs à log2(N)
* E est un ensemble d'entiers non-vides --> il admet un plus petit élément, noté n
* On a U(n) = 2^n > N
* Pour tout k>0, U(n+k) = U(n) * 2^k > U(n) > N
==> Pour tout entier N, il existe un certain rang n à partir duquel la suite U est toujours supérieure
==> La suite diverge

C'est une construction mécanique à partir d'axiomes.

Vu que tout le monde en parle dans sa réponse : il n'a pas été prouvé que Syracuse converge, il n'a pas été prouvé que Syracuse diverge, et il n'a pas non plus été prouvé que c'était indémontrable, si ? (ou alors j'ai raté une info capitale)

Et donc, peut-être qu'on peut le démontrer de manière automatisée (dans le sens "ça n'est pas impossible de le faire"), bien qu'on n’arrive pas aujourd'hui à formaliser cette démonstration. Un certain théorème a bien attendu 400 ans et l'arrivée des courbes elliptiques avant d'être prouvé, il n'était pas considéré comme indémontrable entre-temps (indémontrable dans le sens "je peux prouver qu'il n'existe pas de démonstration")

Quoi qu'il en soit, je ne parle pas de convergence mais de constance. Je peux très facilement prouver que la suite de Syracuse ne devient jamais constante. La preuve tient en deux lignes.
Soit k une valeur de départ de la duite de Syracuse, soit U_k(n) un terme quelconque de cette suite.
--- Soit U(n) est pair, dans ce cas U_k(n+1) = U_k(n) / 2, donc U_k(n+1) ≠ U_k(n) (sauf si c'est 0, on peut ajouter quelques lignes pour prouver que si k≠0, alors U_k(n) aussi)
--- Soit U(n) est impair, dans ce cas U_k(n+1) = U_k(n) * 3 + 1, donc U_k(n+1) ≠ U_k(n) (sauf si c'est -1/2, mais ça n'est pas acceptable)

--> Conclusion : il n'y a pas deux termes consécutifs égaux. La suite ne peut donc pas devenir constante.

A la rigueur, la suite S3 qui regarde 3 termes plus loin sur Syracuse peut convenir. Mais encore une fois, prouvez-moi que c'est indémontrable (ou tentez autre chose)

Hélas Scarta, ce matin je me disaisbien que l'argument de la suite de Syracuse était un peu faible.

Justement parce que si jamais un jour on parvient à démontrer sa convergence pour tout Uo, le contre exemple - choisi par tout le monde ici apparemment - tombe à l'eau.

Bon ben, reste à chercher.

Tu écris
[@Aunryz: comme indiqué
U(n+1) = [U(n)/2] -- c'est à dire la moitié, arrondie à l'inférieur
C'est juste un exemple de suite qui devient constante]

C'est justement la notation qui m'a interrogé
j'ignorais que les crochets [] avaient le sens de l'arrondi inférieur (partie entière)
(J'en étais resté à E() accessible au clavier)

Et je voulais aussi savoir ce que tu acceptais comme opérations (et notamment pour la partie entière) dans les suites sur lesquelles on peut se pencher.

@Aunryz : c'est une bonne remarque. Disons que toutes les opérations mathématiques et logiques sont valides.
Sinon, c'est vrai qu'on peut rentrer dans certains paradoxes. Par exemple en utilisant le paradoxe de Berry ou le paradoxe de Richard.

U(n)=le plus petit nombre qu'on ne peut décrire avec n caractères.

Vu que chaque terme n'est pas vraiment calculable, ça va être rock'n roll de trouver si ça converge

@Zindy : on peut oui tendre vers une limite sans jamais l'atteindre.
Par exemple, U(0)=1, U(n+1) = U(n)/2 tend vers 0 mais ne l’atteint jamais.
Ta fonction f serait alors f(x)=x/2, point fixe pour x=0, mais ça ne t'aide pas.

Tout ce que tu peux dire, c'est que si la suite atteint cette valeur, alors elle deviendra constante. Mais le peut-elle ?
Dans le cas f(x) = x/2, tu peut facilement vérifier que l'antécédent de 0 est aussi 0, et donc si U(n)=0 pour un certain n, alors U(n-1) aussi etc, jusqu'à U(0) = 0 alors qu'il vaut 1.
On vient donc de démontrer de manière formelle que cette suite ne devient pas constante.

Attention : personne n’a démontré qu’elle n’était pas démontrable. Donc jusqu’à preuve du contraire elle l’est.

Par « résultat non démontrable », on entend habituellement « résultat dont on a prouvé que s’il est vrai, alors la théorie mathématique dans laquelle on est reste cohérente, et idem s’il était faux ».

Exemple : les 5 axiomes d’Euclide sont 5, parce qu’on a fini par prouver (après 2000 ans) qu’aucun ne peut être prouvé par les 4 autres. On peut considérer qu’un axiome est faux, et on obtiendra une géométrie tout à fait valide (quoique assez abstraite)

Merci pour la ballade
tu m'as donné l'occasion d'aller voir du côté de ce problème de l'arrêt de Turing

Mais je n'ai pas pensé que cela pouvait être la solution
bêtement je cherchais encore à produire une suite

ce qui m'a donné (je viens de voir que tu as donné ta réponse)

U(1) = produit des 2 premières décimales de pi modulo 26  + 64
U(3) = produit des 2 suivantes …
U(4) = idem
V(0) = Car(U(1)&Car(U(2)& … s’arrête lorsque pour la valeur de n = n0  tel que U(n0) = 64
V(1) = Car(U(n0+1) & Car(U(n0+2) … s’arrête lorsque pour la valeur de n = n1 on a U(n1) = 64
W(0) = 1 si V(0) est sur internet, sinon W(0) = 0
W(n) = 1 si V(N) est sur internet, sinon W(N) = 0

(oui, ... bon (sourire)²)


et ... (un détour par Borges et sa bibliothèque de Babel)

(la bible est ici considérée sans ponctuation)
U(0)= 1ère caractère de la bible
U(1)= 2ème caractère de la bible
U(2)= 3ème caractère de la bible (un espace)
V(n)= place de U(n) dans l’alphabet , si U(O) est un espace alors V(0)=27
W(0)= V(0)
W(n)=nombre obtenu par concaténation des termes de V(0) à V(n)

Z(n) = 1 si W(n) se trouve dans la séquence des décimales de pi), sinon 0


(mais toujours ce problème de "pas démontré que c'est pas démontrable, à savoir  pi nombre univers)

[ou
A(n) = 1 si W(n) se trouve dans la séquence des décimales d'UN des termes de la suite B(m) = 1 + 1/2 + 1/3 + ... 1/m ]

_________________________
Tu écris "Et donc la conséquence : soit on vient de prouver que les réels sont contenus dans les entiers, soit il y a des nombres "incalculables"

On frôle ici l'axiome de choix ?

« Il existe des résultats indécidables » : on est d’accord.
Mais à mon humble avis, ça n’est pas plus fort que ce que montre Turing (en l’occurrence que l’arrêt est indécidable). « Il en existe » ne prouve pas que « celui-là l’est ».
Note que l’énoncé de Turing n’est pas non plus plus fort que l’énoncé général. C’est différent c’est tout. Comme si on disait « Il existe des entiers naturels » et « 3 est un entier naturel ».

Quant à la « variante » de Syracuse qui est indécidable, en réalité une version « généralisée », Conway a effectivement démontré que ça n’était pas décidable.
La version généralisée dit en gros : suivant une valeur de i modulo n, on va avoir n équations affines d’un terme vers le suivant.
Et pour savoir si on peut démontrer la convergence pour toutes ces suites, quelques soient les règles, … plot twist … Conway a démontré que c’était équivalent justement au problème de l’arrêt ! Donc indécidable.
(D’où ma réflexion sur la démo quand tu as parlé des familles de Conway et la référence faite à Turing derrière).

Edit : j’aurais voulu mettre un lien vers la démonstration de John Conway, j’ai cherché pas mal mais elle est introuvable. Je sais qu’elle est publiée dans un volume disponible à la bibliothèque universitaire du coin (en tout cas il l’était il y a 20 ans que je l’ai lu la 1ere fois). A l’occasion j’irai la scanner.
En gros, quelle que soit une machine de Turing et la valeur qu’on passe en entrée, Conway arrive à sortir une fonction de style Collatz (avec des facteurs différents) donc chaque nombre successif correspond à l’état de la machine étape après étape. Et donc puisque l’arrêt est indécidable pour toutes les machines, il existe au moins une machine qu’ont l’arrêt est indécidable et il existe aussi une fonction de collatz dont la convergence est indécidable.