Qui aime la physique ou les mathématiques?

Je l'ai feuilleté rapidement sans le lire. A mon sens c'était un peu n'importe quoi: une agglomération de critiques plus idéologiques que mathématiques. D'ailleurs, il fait l'erreur classique de dire que le réel construit par argument diagonal sans faire attention aux suites infinies de 9 est distinct de tous les autres car il diffère d'eux par au moins une décimale. Mais bon, je ne l'ai pas lu.

Qu'est-ce qui ne te convainc pas dans l'argument de la diagonale?

paela a écrit: D'ailleurs, il fait l'erreur classique de dire que le réel construit par argument diagonal sans faire attention aux suites infinies de 9 est distinct de tous les autres car il diffère d'eux par au moins une décimale.

En quoi est ce que c'est là une erreur ? Le procédé diagonal dans sa logique, ne fait pas cette distinction. La distinction a été faites quand quelqu'un a (enfin ?) trouvé un moyen de prouver que quelque chose ne fonctionnait pas ...

- regardez, ça ne fonctionne pas !!!
- mmm, ah mais il suffit de faire attention quand les réels se terminent par certaines suites particulières !!
-... et merde. Maintenant il va falloir que je trouve autre chose. Mais ça ne te choque en rien qu'on ait ainsi prouvé que le raisonnement initial était faux ?
- non.

---

Un truc qui me turlupine, c'est qu'on peut considérer un réel au hasard parmi l'ensemble [0,1[

Et là il est possible d'observer la suite des éléments de son développement en base 2.

D'un autre coté, il est aussi possible de tirer un réel au hasard, en se donnant à priori une liste infinie d'éléments binaires indépendants, qui vont décrire son développement.

Du coup, la seconde méthode, devrait être un peu moins uniforme que la première (puisque certains des réels obtenus sont équivalents entre eux). Je trouve ça assez troublant. Et pour tout dire contre intuitif. Moi j'ai envie de postuler que les deux méthodes de tirage sont strictement équivalentes. Mais si c'était le cas, j'ai l'impression qu'il faudrait à nouveau ajuster le procédé diagonal. Par exemple par l'astuce que dans le cas général c'est faux.

Si on formalise classiquement ton problème, la première méthode (choisir au hasard dans [0;1[) donnera une probabilité nulle de "tomber sûr" un rationnel, et une probabilité de 1 de tomber sur un irrationnel. (parce que justement l'ensemble des rationnels est dénombrable tandis que l'ensemble des irrationnels ne l'est pas)
La seconde produira le même effet: même si parmi les suites éventuellement périodiques il y a des couples qui représentent le même rationnel, comme deux fois zéro donne toujours zéro cela ne change rien. Mais bon cette question de choix d'un réel au hasard dans [0;1[ n'a pas grand sens sauf en maths où elle est formalisée.

Si pour toi le procédé diagonal est la démonstration erronée (sans s'assurer qu'on ne produit pas une suite avec des 9 à la fin) du fait que l'ensemble des réels n'est pas dénombrable, alors oui c'est tout simplement une fausse démonstration (autrement dit, ce n'est pas une preuve). Je ne sais pas pourquoi il est utilisé tel quel par beaucoup de vulgarisateurs.

paela a écrit:
Si pour toi le procédé diagonal est la démonstration erronée (sans s'assurer qu'on ne produit pas une suite avec des 9 à la fin) du fait que l'ensemble des réels n'est pas dénombrable, alors oui c'est tout simplement une fausse démonstration (autrement dit, ce n'est pas une preuve). Je ne sais pas pourquoi il est utilisé tel quel par beaucoup de vulgarisateurs.

On sait que deux développements distincts en une infinité de points peuvent être égaux, on le sait du fait de travaux qui n'avaient rien à voir avec le procédé diagonal.

Est ce qu'il existe une preuve que le procédé diagonal fonctionne, une fois qu'on a supprimé cette anomalie (deux valeurs différentes peuvent être identiques) dictée par une autre branche des mathématiques ? Pourquoi est ce que cette preuve n'avait pas identifié cet écueil ?

On peut développer 0.1 en 1000000.... ou en 099999..., qui sont des développements qui diffèrent en une infinité de points (tous). La règle est que deux développements décimaux par défaut distincts (en au moins un point) représentent deux réels distincts.
Une suite de chiffres est le développement décimal par défaut d'un réel dans [0;1[ si et seulement si elle ne finit pas par que des 9. Ainsi pour être sûr que la suite produit représente un réel qui n'est pas dans la liste, il suffit de s'assurer qu'elle ne finit par que par des 9.



Je ne comprends pas ta première question, et pour la seconde c'est tout simplement que cette "preuve" est fausse, et que les gens qui la présentent se trompent ou oublient de préciser ce qu'il faut. A mon avis la raison est simplement que les gens sont habitués à la mauvaise preuve et ne se posent pas plus de question que ça à ce niveau. Parfois ce qu'on voit est une construction qui produit bien une suite sans 9 à répétition, mais qui ne précise pas que c'est important; et souvent, les preuves identifient les réels et leur développement sans faire attention à cette petite subtilité.

paela a écrit:

Si x est un réel dans [0;1[, le développement décimal par défaut de x est la suite u définie pour tout entier naturel n par u(n) = E(10^(n+1).x) - 10.E(10^n.x).
Où E(t) est le plus grand entier plus petit que t, ou encore l'unique entier tel que E(t) <= t < E(t)+1; par ex E(1/2) = 0, E(1) = 1, E(4/3) = 1.
On peut montrer que x est la limite de la somme u(0)/10 + ... + u(n)/10^(n+1) et que u est la seule suite ne finissant pas que par des 9 satisfaisant cette propriété. Mais comme on peut le voir avec 0.1= 0.0999... , il n'y a pas unicité si on tolère les suites finissant par des 9.

Y a a peine un quart de la démonstration, peux-tu lire le journal si je je divise en quatre parties égales et que je t'en donne qu'une seule ?

Je donne juste ça pour qu'on soit clair sur les définitions, les démonstrations se trouvent sur internet: développement décimal d'un réel.

Pour parler un peu d'autre chose, je me demandais comme ça, est ce que vous pensez que la suite suivante converge ? Est ce que tous les termes sont des nombres transcendants ? Existe t'il une cyclicité ?

S(0)= La suite des termes de la partie non entière du développement en base 2 de PI.
S(n)= La suite des termes pairs de la suite S(n-1)


Exemple
S(0) = 0010010000 1111110110 ....
S(1) = 0010011110 ....
S(2) = 00110 ...
S(3) = 01 ..

Et du coup, j'aurais tendance à vouloir généraliser la question pour tout nombre transcendant au niveau de l'initialisation de S(0)

---

Si on prend un échiquier (8x8 cases), et qu'on enlève deux cases quelconques, il reste alors 62 cases. Cela doit permettre de placer 31 dominos (un domino occupe deux cases adjacentes), à priori. Comment vous y prendriez vous dans le cas général pour disposer les 31 dominos ?

Dur de comprendre la pertinence de cette suite, mais je répondrais non à toutes tes questions. Simplement en me basant sur le fait que les décimales de PI sont sensées être "aléatoires" et donc si tu en prends une sur deux ou une sur dix mille ou ce que tu veux, ça te donnera toujours une suite aléatoire. Mais en fait je me demande bien à quelle notion de convergence tu fais allusion dans ta question. Qu'est ce que ça veut dire qu'une suite de suite de chiffres binaires converge pour toi ?

stupeflip666 a écrit:Dur de comprendre la pertinence de cette suite, mais je répondrais non à toutes tes questions. Simplement en me basant sur le fait que les décimales de PI sont sensées être "aléatoires" et donc si tu en prends une sur deux ou une sur dix mille ou ce que tu veux, ça te donnera toujours une suite aléatoire. Mais en fait je me demande bien à quelle notion de convergence tu fais allusion dans ta question. Qu'est ce que ça veut dire qu'une suite de suite de chiffres binaires converge pour toi ?

Ben déjà si la suite devient constante au delà d'un certain rang :p
En l'écrivant, je me suis bien rendu compte que la question n'était pas forcément super intéressante en elle même. Mais juste la remarque "PI est une suite 'aléatoire'" est intéressante.

http://villemin.gerard.free.fr/Wwwgvmm/Geometri/PiPropri.htm a écrit:
Les 16 millions de décimales analysées ont passé avec succès tous les tests de caractère aléatoire connus

C'est quoi "les tests de caractère aléatoire connus" ?

Il ne semble pas exister de "preuve" ici, juste un constat empirique.

Simon Plouffe a écrit:
En 1995, il découvre la formule de Bailey-Borwein-Plouffe (BBP) qui permet de calculer le n-ième bit de π sans avoir à calculer d'autres bits. Un an plus tard, il publie un nouvel article sur la formule, permettant de déterminer le n-ième chiffre en base 10 de π, mais le temps de calcul, bien que relativement court, n'est pas linéaire.
Il est également un coauteur de l'Encyclopédie en ligne des suites de nombres entiers.
L'Inverseur de Plouffe était une page web qui contenait plus de 200 millions de constantes mathématiques. Un répertoire était accessible et contenait plus de 3,93 milliards de constantes à une précision de 64 chiffres décimaux au 21 juillet 2009.
Pour l'anecdote, Simon Plouffe a détenu en 1977 le record Guinness de mémorisation des décimales de π, avec 4 096 décimales. Il en avait mémorisé 4 400, mais en a récité seulement 4 096 parce que « c'est un beau nombre » (4 096 = 212).
Simon Plouffe est le neveu du pianiste canadien Pierre Brabant.

The Bailey–Borwein–Plouffe formula (BBP formula) is a spigot algorithm for computing the nth binary digit of pi (symbol: π) using base 16 math. The formula can directly calculate the value of any given digit of π without calculating the preceding digits.
The discovery of this formula came as a surprise. For centuries it had been assumed that there was no way to compute the nth digit of π without calculating all of the preceding n − 1 digits.

https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula a écrit:
there is no systematic algorithm for finding the appropriate combinations; known formulas are discovered through experimental mathematics

Though the BBP formula can directly calculate the value of any given digit of π with less computational effort than formulas that must calculate all intervening digits, BBP remains linearithmic whereby successively larger values of n require increasingly more time to calculate; that is, the "further out" a digit is, the longer it takes BBP to calculate it, just like the standard π-computing algorithms

Stauk a écrit:Pour parler un peu d'autre chose, je me demandais comme ça, est ce que vous pensez que la suite suivante converge ? Est ce que tous les termes sont des nombres transcendants ? Existe t'il une cyclicité ?

S(0)= La suite des termes de la partie non entière du développement en base 2 de PI.
S(n)= La suite des termes pairs de la suite S(n-1)


Exemple
S(0) = 0010010000 1111110110 ....
S(1) = 0010011110 ....
S(2) = 00110 ...
S(3) = 01 ..

Et du coup, j'aurais tendance à vouloir généraliser la question pour tout nombre transcendant au niveau de l'initialisation de S(0)

Ca a l'air intéressant, je ne comprends pas bien ta définition ton passage, ta définition de S(n+1) en fonction de S(n), tu coupes le nombre en bloc ?
SInon il n y a pas de cyclicité sinon cela serait un rationnel

Stauk a écrit:
Si on prend un échiquier (8x8 cases), et qu'on enlève deux cases quelconques, il reste alors 62 cases. Cela doit permettre de placer 31 dominos (un domino occupe deux cases adjacentes), à priori.  Comment vous y prendriez vous dans le cas général pour disposer les 31 dominos ?

Sous-entendu tout remplir, c'est impossible 63 n'est pas divisible par 2.

Ca a l'air intéressant, je ne comprends pas bien ta définition ton passage, ta définition de S(n+1) en fonction de S(n), tu coupes le nombre en bloc ?
SInon il n y a pas de cyclicité sinon cela serait un rationnel

Il prend un chiffre sur deux de la suite précédente pour construire la nouvelle suite.

Stauk a écrit:
Si on prend un échiquier (8x8 cases), et qu'on enlève deux cases quelconques, il reste alors 62 cases. Cela doit permettre de placer 31 dominos (un domino occupe deux cases adjacentes), à priori.  Comment vous y prendriez vous dans le cas général pour disposer les 31 dominos ?

Sous-entendu tout remplir, c'est impossible 63 n'est pas divisible par 2.

Heu tu fais exprès de ne pas comprendre les questions à chaque fois ? c'est un nouveau jeu sur le forum ? Depuis quand 64-2 = 63 ??

Sinon clairement la suite ne sera pas constante à partir d'un certain rang, sinon PI n'aurait pas pu passer avec succès tous les tests statistiques auxquels un gars faisait allusion

Moi je kiffe le théorème de Pythagore ^_^

stupeflip666 a écrit:

Ca a l'air intéressant, je ne comprends pas bien ta définition ton passage, ta définition de S(n+1) en fonction de S(n), tu coupes le nombre en bloc ?
SInon il n y a pas de cyclicité sinon cela serait un rationnel

Il prend un chiffre sur deux de la suite précédente pour construire la nouvelle suite.

Stauk a écrit:
Si on prend un échiquier (8x8 cases), et qu'on enlève deux cases quelconques, il reste alors 62 cases. Cela doit permettre de placer 31 dominos (un domino occupe deux cases adjacentes), à priori.  Comment vous y prendriez vous dans le cas général pour disposer les 31 dominos ?

Sous-entendu tout remplir, c'est impossible 63 n'est pas divisible par 2.

Heu tu fais exprès de ne pas comprendre les questions à chaque fois ? c'est un nouveau jeu sur le forum ? Depuis quand 64-2 = 63 ??

Sinon clairement la suite ne sera pas constante à partir d'un certain rang, sinon PI n'aurait pas pu passer avec succès tous les tests statistiques auxquels un gars faisait allusion

C'est marrant, j'avais lu qu'on enlevait une case, mal lu certainement  
Sinon la question qu'on pourrait poser à Stauk, à partir de quel ordre il obtient une suite constante, sur combien de chiffres significatifs, il travaille ?
Après on ne peut présumer de rien ...


@Stauk
Tu pars d'une position où les deux trous forme un espace où tu pourrais y placer un domino, un trou doit déjà avoir trouver sa position final disons le trou 1, tu déplaces continûment le trou 2 vers la destination que tu désires, mais toutes les configurations ne sont pas possibles donc la position est peut être impossible.

j'ai rien compris à la réponse de prométhéus mais de toute façon je le soupçonne de raconter absolument n'importe quoi juste pour le plaisir. Sinon voilà ma solution pour le problème des dominos :
les deux trous encadrent un certain rectangle, dont une des dimensions doit être paire et l'autre impaire, sinon le problème est impossible (un trou doit être sur une case blanche et l'autre sur une case noire de l'échiquier pour espérer pouvoir paver le reste avec des dominos)
Sans perte de généralité (j'adore cette phrase) on peut supposer que c'est la dimension horizontale qui est impaire.
On va essayer d'abord de remplir l'intérieur du rectangle. On complète d'abord la 1ère et la dernière ligne qui privées chacune d'une case (à cause des trous) sont donc de longueur paire, donc facile à paver. Sur le rectangle qui reste, on peut paver la première colonne verticalement qui est de hauteur paire. Ce qui est reste est de dimension paire dans les deux dimensions et donc facile à paver.
Ensuite on peut rajouter des lignes et colonnes au rectangle à l'extérieur pour rendre l'espace restant facile à paver. Je ne rentre pas dans les détails mais ça semble très facile. Et voilà !

...

Père Marc en Poulet a écrit: c'est un Ecossais (James Gregory) qui remarqua que la fonction arctan correspondait à une suite infinie de fractions sur la base de suites mathématiques harmoniques. Personne ne sait comment il s'y est pris. Du pur génie !

La démonstration sera faite par Taylor (d'où le nom éponyme de ladite série). Et c'est le philosophe et mathématicien Leibniz qui développera le procédé pour calculer la valeur exacte de PI. Newton fera de même de son côté en suivant un procédé analogue.

Dans la catégorie formules bizarres qui ne sortent de nulle part ... "j'ai eu l'intuition que ça marcherait". Ah ouais ? Bon ben t'as de bonnes intuitions alors.

Une question que m'a proposé quelqu'un :
- Etant donné un objet X composé d'une infinité de {0 ou 1}
(exemple 0000111001010111001 ....)

Est t'il possible de construire une relation "inférieur ou égal", avec un plus petit élément sur l'ensemble des X
J'avais envie de lui proposer la construction suivante, qu'en pensez vous ?

Deja on pourrait compter le nombre de 1, soit il est fini, soit il est infini.
Quand le nombre de 1 est fini, on peut dire "un x0 de X avec plus de 1 est toujours supérieur à un x1 qui comporte moins de 1"
Pour deux éléments de X avec le même nombre de 1, on peut simplement utiliser le développement binaire  somme( bit_numero_n*(1/2^n) ) pour ordonner (ça donne un réel dans 0,1 qu'on peut ordonner facilement)
autrement dit : considérons le premier bits, s'il est a 1 alors il est supérieur à tous les X qui ont le premier bit à 0. Sinon, on considère le second bit ... puis le troisième s'il sont égaux, etc ..

Une fois qu'on a ça, on a donc ordonné les X avec un nombre fini de 1.
Les X avec un nombre infini de 1 peuvent être divisés en deux catégories :
avec un nombre fini de 0, avec un nombre infini de 0.

Si le nombre de 0 est fini, on va utiliser la même règle que pour le nombre fini de 1 en inversant simplement les bits(de toute façon les deux ensembles sont en bijection, par simple inversion des bits).

On pose que quand il y a un nombre fini de 0 dans x1, alors si x0 a un nombre fini de 1 alors x1 > x0

Reste les X avec un nombre infini de 0 et un nombre infini de 1,
pour ceux là on va les considérer supérieurs aux deux autres sous ensembles
Maintenant, etant donné deux X x0 et x1 avec nombre infini de 0 et de 1 ...
on utilise à nouveau somme (bit_numero_n*(1/2^n)) pour les ordonner.

L'ensemble résultant X a donc bien un plus petit élément (000000....), et chaque paire x0,x1 de l'ensemble des X est comparable via le procédé décrit ci dessus.

Ton objet X, c'est l'ensemble des suites sur {0, 1}.

Il y a déjà un ordre simple sur cet ensemble, l'ordre lexicographique des séquences d'éléments ordonnés (0 < 1) étendu à un nombre infini d'éléments.

Ainsi :
— x = y si x_i = y_i pour tout i;
— x < y s'il existe j tel que x_i = y_i pour i < j et que x_j < y_j.

Il n'y a pas de garantie que l'algorithme de vérification que x ⩽ y termine, forcément.

Pour le reste, je regarde plus attentivement. Mais, en dehors du problème tel qu'il est posé, on peut se demander à quoi pourrait servir un tel ordre. C'est-à-dire : avec quelle structure sur X que l'on voudrait construire serait-il compatible ?

Pieyre a écrit:C'est-à-dire : avec quelle structure sur X que l'on voudrait construire serait-il compatible ?

La question c'était de savoir s'il en existe un.

dans le cas général, l'existence repose sur l'axiome du choix. Donc quelque part, il me posait la question "est ce qu'on est à ton avis dans le cas général ou pas". Et bien sûr j'avais envie de répondre non. Mais comme la discussion n'est pas allée jusqu'au bout, je n'ai pas eu le temps de savoir exactement ce qu'on devait faire ensuite !

Si on est dans le cas général, et qu'on peut construire une solution sans faire appel à l'axiome du choix, alors y a un truc qui ne va pas quelque part. Enfin je pense. Bref. Est ce que la solution fonctionne ou pas, telle est la question, qui m'aidera à reprendre la conversation, si jamais je recroise la personne.

Il s'agissait probablement de savoir s'il existe un ordre pour lequel tout ensemble contenant au moins une suite admet un plus petit élément.
Avec le tien, par exemple, l'ensemble contenant les suites X1= 10101010... X2 = 100100100100... X3 = 1000100010001000... etc n'a pas de plus petit élément.

En effet, ce n'est pas un bon ordre.

Maintenant, Stauk, ma question portait sur le fait qu'un tel ordre serait ou non compatible avec une opération sur les éléments de X, par exemple avec une addition.

les suites infinies de 1 et de 0 sont en bijection avec les parties de N
(le 1 représente l'inclusion d'un élément de N, et le 0 son exclusion).

Donc trouver une façon de bien ordonner X devrait être équivalent à trouver une façon de bien ordonner les parties de N. Mais ... pour qu'un ensemble soit bien ordonné, il faut que toute partie non vide de l'ensemble possède un plus petit élément ....

Avec le sous ensemble : nombre infini de 1 et de 0, ce n'est pas très clair de déterminer précisément à quoi ressemblerait le plus petit élément avec l'ordre total fourni. Sauf s'il existe un procédé que j'ignore, naturellement (avec les mathématiciens, je m'attends à tout !)

Edit : Encore que .... une suite infinie de 0 concaténée avec une suite infinie de 1 j'imagine pourrait faire l'affaire. C'est bien un élément de l'ensemble (heu ... oui, non, peut être ?) , et on ne peut pas trouver plus petit. Si on considère que cet élément est bien valide,

Edit 2 : du coup on va logiquement examiner le sous ensemble qui exclu ce plus petit élément, et maintenant quel est le plus petit élément de ce nouvel ensemble ? On rigole moins là d'un coup.

Pieyre a écrit:En effet, ce n'est pas un bon ordre.

Si l'on considère la bijection entre les suites x = (x_i) et les nombres réels écrits en base 2 ayant la forme 0,x₁... x_n... est-ce que cela ne simplifie pas le problème ? L'ordre des réels correspond à la fois à l'ordre lexicographique et à celui des sommes des 1/(2^x_i) où x_i ≠ 0.

Maintenant, si l'on s'intéresse uniquement au nombre de 0 et de 1 dans les suites plutôt qu'a leur rang dans ces suites, comment distinguer entre les suites comportant un nombre infini de 0 et de 1, comme celles indiquées par Paela ? Est-ce que cela ne revient pas à se demander quelque chose du genre : y a-t-il davantage d'entiers ou d'entiers pairs ?

Dans cette perspective, on peut être conduit à étudier la proportion des 1 dans chaque suite sur un intervalle des rangs [1, n] et à faire tendre n vers l'infini. De cette façon on peut obtenir un ordre sur les suites qui correspondent, selon le développement en base 2, aux rationnels (puisque leur développement est périodique), mais en obtenant que des suites différentes puissent égales au sens de cet ordre. Quant aux nombres transcendants, on ne peut pas tous les ordonner ainsi. En effet, il faudrait prouver la convergence du procédé.

STAUUUUUkkkkkkk

Stauk a écrit:Une question que m'a proposé quelqu'un :
Est t'il possible de construire une relation "inférieur ou égal", avec un plus petit élément sur l'ensemble des X

La contrainte "avec un plus petit élément" n'apporte rien car une fois que tu as une relation d'ordre, tu peux toujours ajouter un nouvel élément "0" et décréter qu'il est plus petit que tous les autres.
Donc la vrai question vraissemblablement était de savoir si l'ensemble en question, qui est équivalent à l'ensemble des réels R peut être bien ordonné. Et si mes souvenirs sont bons, ce doit être le genre de question où on peut démontrer de façon indirecte et abstraite que R peut être bien ordonné, mais il est absolument impossible d'exhiber une construction qui implémente concrêtement ce bon ordre. J'ai pas vérifié donc possible que je raconte n'importe quoi ce sont justes de vagues pseudos souvenirs....

En poussant un peu la réfléxion (la psychanalyse dirait mon interlocuteur mathématicien ..), je me rend compte que le problème que j'ai, est avec le concept d'égalité. Le signe =

Quand on me dit soit deux nombres entiers a et b, n'importe lesquels, tels que a=b .. j'arrive à comprendre.

Quand on me dit, soit deux éléments de l'ensemble des parties des parties de N (entiers naturels), a et b, tels que a=b, je n'ai pas trop de doutes que je ne comprends pas de quoi on cause ...

Quand on me dit, soit deux parties de n distinctes, a et b, telles que a=b, j'ai le sentiment qu'on est en train de m'entourlouper sévère.




Du coup mon problème avec les histoires de diagonalisation est sans doute là :
- Soit une liste de nombres réels (ou parties de N mettons, c'est pareil).
- Nous construisons maintenant un nouvel élément (appelons le b) par le procédé diagonal, à partir de cette liste ...

Et on propose : quelque soit "a" de la liste, alors on peut affirmer que (a=b) est faux.
Sauf que je me sens arnaqué, du fait qu'on ne m'a pas vraiment convaincu de ce qui est entendu précisément par le soit disant booléen (a=b).

stupeflip666 a écrit:ce doit être le genre de question où on peut démontrer de façon indirecte et abstraite que R peut être bien ordonné

Wikipedia nous informe :

Mr Wikipedia a écrit:
L'axiome du choix est souvent utilisé par l'intermédiaire de l'un des deux énoncés suivants qui lui sont équivalents :

Théorème de Zermelo : « Tout ensemble non vide peut être muni d'une structure de bon ordre » ;
Lemme de Zorn : « Tout ensemble inductif non vide admet un élément maximal ».
On montre facilement que le théorème de Zermelo implique l'axiome du choix : comme pour les entiers naturels, si E est muni d'un bon ordre, le minimum pour celui-ci fournit une fonction de choix sur l'ensemble des parties non vides de E (second énoncé équivalent). De même le lemme de Zorn a également facilement pour conséquence l'axiome du choix.

Another argument against the axiom of choice is that it implies the existence of objects that may seem counterintuitive.[8] One example is the Banach–Tarski paradox which says that it is possible to decompose the 3-dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original. The pieces in this decomposition, constructed using the axiom of choice, are non-measurable sets.

https://fr.wikipedia.org/wiki/Paradoxe_de_Banach-Tarski

En mathématiques, et plus précisément en géométrie, le paradoxe de Banach-Tarski est un théorème, démontré en 1924 par Stefan Banach et Alfred Tarski, qui affirme qu'il est possible de couper une boule de l'espace usuel R^3 en un nombre fini de morceaux et de réassembler ces morceaux pour former deux boules identiques à la première, à un déplacement près. Ce résultat paradoxal implique que ces morceaux soient non mesurables, sans quoi on obtiendrait une contradiction (le volume étant un exemple de mesure, cela veut plus simplement dire que ces morceaux n'ont pas de volume).

La démonstration de ce résultat utilise l’axiome du choix, nécessaire pour construire des ensembles non mesurables.

Pour dire les choses rapidement, en maths, tous les objets ou presque sont définis comme des ensembles ayant certaines propriétés. L'axiome d'extensionnalité de la théorie des ensembles dit que deux ensembles sont égaux si et seulement s'ils ont les mêmes éléments.

Cela s'applique aux réels, mais les définitions d'un réel en tant qu'ensemble sont un peu compliquées (pour la plus simple que je connais, ce sont des ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles ou seul le rez-de-chaussée peut être l'ensemble vide) qu'on utilise des critères pour montrer rapidement que deux réels sont différents. En particulier, deux réels sont différents si et seulement si leurs développements binaires (voir précédemment) sont différents en au moins une valeur.

paela a écrit:En particulier, deux réels sont différents si et seulement si leurs développements binaires (voir précédemment) sont différents en au moins une valeur.

Si je comprends bien la question, l'op ne comprend pas la notion d'égalité entre deux développements binaires de réels quelconques dont on ne connait rien d'autre que leur développement binaire. C'est à dire qu'étant donné deux boîtes noires qu'on peut interroger pour en extraire les coefficients binaires un par un, comment faire pour déterminer que les deux développement associés sont égaux ? (c'est impossible, phénomène bien connu en programmation, on ne teste jamais l'égalité entre deux nombres à virgules flottantes : ça ne sert à rien). A partir de là la notion de "différent en au moins une valeur", devient suspecte (il se trouve qu'en prime pour les Réels, elle est parfaitement fausse, mais c'est un détail, on peut toujours ne considérer que les suites des coefficients, sans passer par les bizarreries des égalités entre réels). Parler de différence, quand on n'a pas de moyen de décrire ce que c'est qu'une égalité, ça ressemble soit à un abus de langage, soit à une tautologie (qui affirmerait grosso modo que deux réels dont on en connait que le développement binaire sont toujours différents, à moins d'être supposés égaux)

Enfin c'est mon interprétation.

Donc grosso modo, tu poses ici la notion de "différence", mais qui est toujours vrai. Puisqu'on est toujours libre de supposer que deux réels dont on ne connait que la liste des coefficient binaires sous la forme d'une suite infinie de 0 et de 1 non reliés par une formule vérifie la propriété "sont différents en au moins une valeur" (c'est en tout cas ce qui est fait dans les simulations informatiques).


Autrement formulé, le test de l'égalité entre deux réels par la comparaison des chaines binaires infinie associées , semble indécidable en pratique, ce qui rend caduque et illusoire la notion de différence.

De façon amusante, si on décide d'un procédé particulier pour tirer deux Entiers au hasard avec la propriété de pouvoir choisir n'importe lequel, la probabilité de tirer deux fois le même, sera non nulle (pour autant que le procédé ne conserve aucune information entre les deux tirages). A contrario si on fait la même chose avec des réels en se laissant la possibilité de tirer n'importe lequel parmi un sous ensemble continu non ponctuel de réels, on est 100% certain de ne jamais tirer deux fois le même (dans la mesure ou on accepte l'idée que la notion a un sens bien défini - ce qui est vrai dans l'intuition qu'on a de ce qu'est un réel).

C'est un peu comme si en passant de PI à son développement binaire on perdait une information ... le fait qu'il s'agit de PI avec toutes ses propriétés, et de rien d'autre. On ne peut pas reconnaître PI, et en déduire l'ensemble de ses propriétés en observant sont développement binaire en base deux.   Bref le "si et seulement si" semble totalement faux dans ta phrase.

Normalement, un réel est appréhendé selon une formule :
— Sⁿ(0), autrement dit n;
— n/p;
— telle solution d'une équation algébrique;
— pi, e ou autre transcendant défini notamment par une série;
— etc.

À partir d'une telle caractérisation, on peut démontrer que deux réels sont égaux.

Le développement décimal (ou binaire) correspond à divers usages, mais il n'est jamais qu'une façon de caractériser les réels, notamment de les comparer jusqu'à un certain rang, en relation avec la notion de mesure physique.

Grosso modo, un réel et une suite d'entiers c'est la même chose. Deux suites d'entiers U et V sont égales si pour tout indice i, Ui = Vi. Moi ça me semble à peu près clair comme concept, où est le problème exactement ?

fragmentation a écrit:
Si je comprends bien la question, l'op ne comprend pas la notion d'égalité entre deux développements binaires de réels quelconques dont on ne connait rien d'autre que leur développement binaire. C'est à dire qu'étant donné deux boîtes noires qu'on peut interroger pour en extraire les coefficients binaires un par un, comment faire pour déterminer que les deux développement associés sont égaux ?

Là tu regardes le coté informatique et du "comment faire un algo qui soit capable de répondre à la question". Et puis le "une par "une"... pourquoi ? On est tout à fait capable de comparer instantanément 512 bits si ça nous amuse... Pas besoin de proc, de simples portes logiques font l'affaire. Et de toutes façons c'est ce qui est déjà implémenté dans les proc : quand on veut comparer deux réels dans les codes, heureusement qu'il ne faille qu'un seul temps d'horloge et qu'on ne parcoure pas les 64 bits de chaque nombre...

fragmentation a écrit:
(c'est impossible, phénomène bien connu en programmation, on ne teste jamais l'égalité entre deux nombres à virgules flottantes : ça ne sert à rien).

Si, pour les tests de non régression stricts, et aussi pour les systèmes de compression sans perte où c'est bien l'écart (un XOR pour etre plus précis) qui est utilisé entre deux flottants pour encoder l'erreur.

fragmentation a écrit:
quand on n'a pas de moyen de décrire ce que c'est qu'une égalité,  

S'il existe un nombre dans le XOR qui est non nul, ça irait ?

fragmentation a écrit:
Donc grosso modo, tu poses ici la notion de "différence", mais qui est toujours vrai. Puisqu'on est toujours libre de supposer que deux réels dont on ne connait que la liste des coefficient binaires sous la forme d'une suite infinie de 0 et de 1 non reliés par une formule vérifie la propriété "sont différents en au moins une valeur" (c'est en tout cas ce qui est fait dans les simulations informatiques).

Non, pas toujours vrai... du moins pas en informatique, puisque leur codage est fini.

fragmentation a écrit:
Autrement formulé, le test de l'égalité entre deux réels par la comparaison des chaines binaires infinie associées , semble indécidable en pratique, ce qui rend caduque et illusoire la notion de différence.

Toujours pareil : dans le sens du logicien qui cherche une méthode pour le calculer. On parle de maths là, pas d'informatique. Dans ce cas on peut généraliser ce que tu dis à "on ne connait pas pi", "on ne connait pas e", "on ne connait pas sqrt(2)", etc...

fragmentation a écrit:
C'est un peu comme si en passant de PI à son développement binaire on perdait une information ... le fait qu'il s'agit de PI avec toutes ses propriétés, et de rien d'autre. On ne peut pas reconnaître PI, et en déduire l'ensemble de ses propriétés en observant sont développement binaire en base deux.   Bref le "si et seulement si" semble totalement faux dans ta phrase.

Pourtant pi est parfaitement connu et défini dans une base variable (d'euler il me semble, je vais regarder pour le nom).

Je confirme : dans la base d'Euler (http://www.gecif.net/articles/mathematiques/pi/#euler), pi est intégralement connu, il sagit du nombre 2,222222222222222222222222222222...

hobb a écrit:
pour les systèmes de compression sans perte où c'est bien l'écart (un XOR pour etre plus précis) qui est utilisé entre deux flottants pour encoder l'erreur.

... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.

Le xor est une opération bit à bit (donc non applicable aux flottants du fait des contraintes de types, il faut convertir le flottant en autre chose pour pouvoir lui appliquer le XOR) ... donner le nom de l'algorithme auquel tu fais référence me permettrait peut être d'apprendre quelque chose.  

Le coté "non" régression n'est pas tellement pertinent, il s'agit juste de comparer une invariance d'un certain résultat (en gros que les fichiers de sorties sont les même si rien n'a changé).  Si on considère une simulation Montecarlo par exemple, et en supposant qu'on a décidé d'optimiser quelque chose avant de pratiquer la non régression, les valeurs seront bien comparées avec la prise en compte de l'égalité à une marge d'erreur près au moment de la validation par non régression.

Et puis le "une par "une"... pourquoi ? On est tout à fait capable de comparer instantanément 512 bits si ça nous amuse... Pas besoin de proc, de simples portes logiques font l'affaire.

Une par une, ou 512 par 512, c'est pareil en effet, lorsqu'il s'agit de comparer deux chaines infinies.  Le une par une, insiste sur le coté fini de la comparaison partielle, et sur l'aspect incrémental du procédé.

Pourtant pi est parfaitement connu et défini dans une base variable (d'euler il me semble, je vais regarder pour le nom).

Dans la base d'euler, le nombre Pi devient un nombre particulier, je l'ai choisis pour illustrer une chaîne de bits particulièrement chaotique. Si on se met dans la base d'Euler, on peut remplacer Pi par 2 j'imagine, afin d'obtenir une telle chaîne infinie "quelconque" mais dotée par effet de sémantique de propriétés particulières.

stupeflip666 a écrit:Grosso modo, un réel et une suite d'entiers c'est la même chose. Deux suites d'entiers U et V sont égales si pour tout indice i, Ui = Vi. Moi ça me semble à peu près clair comme concept, où est le problème exactement ?

Le problème est que la formule de récurrence (ou autre) qui défini la suite, ne semble pas être équivalente à la liste qui donne les éléments de la suite un par un.
La "preuve" en étant, qu'en disposant uniquement des éléments de la suite sous la forme d'une liste infini (ou chaque terme est fourni, mais de manière indépendante des autres termes, sans formule aucune qui relie les termes), il est impossible de conclure à l'équivalence avec la formule. Dire que les deux représentations sont équivalentes, semble donc inapproprié, en toute rigueur. L'ensemble des formules peut être injectée dans l'ensemble des chaines infinies (les suites infinies d'entiers étant équivalentes aux suites infinies de bits à une transformation près), mais l'ensemble des chaînes infinies ne peut pas être injecté dans l'ensemble des formules.

Ce n'est pas très étonnant, puisque l'ensemble des formules (par récurrence par exemple) est dénombrable, et l'ensemble des chaines infinies d'éléments à valeurs dans un ensemble fini est indénombrable.
Il est donc assez clair qu'il serait faux de supposer une équivalence entre les deux "représentations".

fragmentation a écrit:
... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.

Compression de signaux (image, son, etc). Une publi au pif : https://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf (figure 2).

fragmentation a écrit:
Le xor est une opération bit à bit (donc non applicable aux flottants du fait des contraintes de types, il faut convertir le flottant en autre chose pour pouvoir lui appliquer le XOR) ... donner le nom de l'algorithme auquel tu fais référence me permettrait peut être d'apprendre quelque chose.  

Non, tu peux très bien faire un XOR en C : A ^= B te donne A XOR B dans A, quelque soit le type de A et B (c'est d'ailleurs l'intéret du C : c'est non-typé).

fragmentation a écrit:
Le coté "non" régression n'est pas tellement pertinent, il s'agit juste de comparer une invariance d'un certain résultat (en gros que les fichiers de sorties sont les même si rien n'a changé).  Si on considère une simulation Montecarlo par exemple, et en supposant qu'on a décidé d'optimiser quelque chose avant de pratiquer la non régression, les valeurs seront bien comparées avec la prise en compte de l'égalité à une marge d'erreur près au moment de la validation par non régression.

Il est parfaitement pertinent pour voir si tu n'as pas collé une erreur dans le code quelque part sur une bibliothèque qui n'a pas à intéferer sur les résultats (type MPI, HDF5, ou peu importe). monte-Carlo est un truc marginal, et avec lequel on fait quand meme des tests de non régression stricts (suffit que le seed de la suite est le meme). Par exemple : quand j'ai parallélisé mon code, le fait que le tirage de nombre aléatoires pour chaque proc puisse etre différent a immédiatement foutu en l'air les tests de non-régression. Et en arrangenat ça, ben résultat j'ai corrigé une erreur, et en plus j'ai exactement la meme chose quelque soit le nombre de procs.

Une par une, ou 512 par 512, c'est pareil en effet, lorsqu'il s'agit de comparer deux chaines infinies.  Le une par une, insiste sur le coté fini de la comparaison partielle, et sur l'aspect incrémental du procédé.

si tu connais l'intégralité d'un nombre (en octet), tu n'as pas besoin d'un procédé incrémental. Meme si ça s'apparente plus à une puce dédiée (=> VHDL) qu'à un proc à nombre fixe de bits.

hobb a écrit:

fragmentation a écrit:
... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.

Compression de signaux (image, son, etc). Une publi au pif : https://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf (figure 2).

Je ne connaissais pas du tout ce domaine qui consiste à compresser de grandes listes de flottants, avec un algorithme dédié.
Ton algorithme tend plutôt à confirmer ce que je disais qu'à l'infirmer.

L'algorithme repère une régularité dans la liste des flottants (à compresser), et en déduit une approximation (non exacte ...) du flottant suivant. Si l'approximation est bonne, alors on peut simplement encoder le facteur d'erreur entre la prédiction et le flottant, ce qui peut être fait dans une enveloppe mémoire inférieure à celle qui est nécessaire pour stoker les 64 bits de la double précision des éléments de la liste à compresser.

La particularité de ton algorithme est de ne s'appliquer qu'aux listes de flottants (de taille constante), c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

C'est pas facile la communication

Heu non, ces algos sans perte comme ça, il y en a pléthore : le FLAC, le JPEG2000, etc... Et c'est pas si simple parce qu'il faut aussi envoyer les données compressées en plus des erreurs.

hobb a écrit:Heu non, ces algos sans perte comme ça, il y en a pléthore.

Je ne comprends pas. A quoi tu dis non exactement ? J'ai l'impression qu'on ne parle décidément pas le même langage.
Enfin si tu as d'autres thèses (.pdf en lignes gratuits) à proposer, ça m'intéresse

fragmentation a écrit: c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

Quand tu dis "la majorité". A part la détection des redondances qui ne marche pas pour des images ou des sons (justement parce que ce sont des flottants pour la plupart), quasiment tous les algos sans perte de signaux fonctionnent sur ce principe là. Evidement ce n'est pas applicable à du texte, par exemple. Mais pour l'estimation, le mp3 marche très bien par exemple. Tu rajoutes les sorties XOR et hop ! du FLAC. Idem pour le JPEG => JPEG2000.

Après tu tape sur ton moteur de recherche préféré "compression lossless algorithm XOR PDF" et tu auras ton bonheur ;-)

hobb a écrit:

fragmentation a écrit: c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

Quand tu dis "la majorité". A part la détection des redondances qui ne marche pas pour des images ou des sons (justement parce que ce sont des flottants pour la plupart), quasiment tous les algos sans perte de signaux fonctionnent sur ce principe là. Evidement ce n'est pas applicable à du texte, par exemple. Mais pour l'estimation, le mp3 marche très bien par exemple. Tu rajoutes les sorties XOR et hop ! du FLAC. Idem pour le JPEG => JPEG2000.

Après tu tape sur ton moteur de recherche préféré "compression lossless algorithm XOR PDF" et tu auras ton bonheur ;-)

Comment est ce que tu peux dire ça ? Quand la thèse que tu m'as fourni contredit frontalement ce que tu affirmes ????
Je ne comprends pas. La thèse par exemple compare l'algorithme dédiés aux flotants 64 bits aux algorithmes suivants :

We compare our algorithm to six general-purpose and one special-purpose compressor.

This section briefly introduces these compressors.

rar is an increasingly popular compressor that incorporates a combination of Huffman , LZ77 , and Prediction by Partial Matching  algorithms.
7-zip  is based on the Lempel-Ziv-Markov Chain Algorithm (LZMA)
lzpx  is based on the Lempel-Ziv compression algorithm and uses arithmetic coding.
zzip is a compressor based on the Burrows-Wheeler Transform (BWT)
gzip and bzip2 are a combination of LZ77 and Huffman coding

Ces algos ne sont pas faits pour ça. Tu compares un algo dédié à une suite de réels a des algos type Huffman. Faut comparer ce qui est comparable...

Alors oui, je persiste et signe, LZ et algos similaires ne sont pas utilisés pour les signaux audio/vidéo/etc.

Le xor pour la compression, on l'utilise depuis les années 70, pour te dire...

PS : et la publi (ce n'est pas une thèse) que je t'ai passé ne contredit rien à ce que j'ai dit. Ou alors je serai curieux de savoir où... (mais là tu vas droit dans le mur, je te préviens d'avance...).

hobb a écrit:Ces algos ne sont pas faits pour ça. Tu compares un algo dédié à une suite de réels a des algos type Huffman. Faut comparer ce qui est comparable...
PS : et la publi (ce n'est pas une thèse) que je t'ai passé ne contredit rien à ce que j'ai dit. Ou alors je serai curieux de savoir où... (mais là tu vas droit dans le mur, je te préviens d'avance...).

- Ce n'est pas moi qui compare l'algo dédié à une suite de réels aux algos de Huffman, c'est la publi, que tu m'as proposé pour illustrer les propos. Par ailleurs tu semblais parler des algos généraux de compression (Donc avec même domaine d'application que Huffman), mais tu m'as fourni une publi qui s'applique aux suites de réels de 64 bits.  

Le problème c'est surtout que visiblement tu ne comprends pas grand chose à ce que je raconte (peut être du fait d'un manque d'intérêt ou de temps). Et apparemment tu étais venu sur ce fil à la base, en expliquant que les conversations ne t'intéressaient de toute façon pas. Cela dit j'ai apprécié le fait que tu fournisses cette publi en exemple (j'ignore si tu l'as lu ou si c'était juste un truc pris au hasard sur le net). Certe j'aurais pu la trouver moi même, mais il y a(vait) un coté stimulant à lire un truc qui intervenait spontanément au cours d'une conversation.

En dépit de ces moments agréables, je remarque qu'il est vain qu'on poursuive, car ta façon de communiquer ne me permet pas de rester calme, et il serait tout à fait innoportun qu'on s'enlise plus avant. Ce qui n'est pas à prendre comme un reproche, puisqu' apparemment je fais le même effet à pas mal de monde. J'aimerais juste insister sur mon souhait de clore la conversation et idéalement ne plus en avoir d'autres avec toi.

Je te remercie donc d'avance de ne plus me répondre (étant bien entendu que je lirais ta réponse à ce message s'il y en a une, je la lirais, mais je te répondrais en privée plutôt qu'en public - je m'éfforcerais à l'avenir de ne plus m'adresser à toi en publique, au moins pour un temps) sur des sujets techniques, car le contenu informatif n'est pas à la hauteur du désagréments de tes commentaires.

Pour te donner un exemple :

mais là tu vas droit dans le mur, je te préviens d'avance...

Il n'y a aucune information technique dans cette phrase.
Il y a par contre une menace. Et je n'aime pas qu'on me menace. Je ne vais pas relire tes propos précédents pour tenter de mettre en avant les autres formules qui m'ont dérangé, celle ci est à mon sens parfaitement représentative de ce que j'ai retenu de cet échange.

Bon, je vais reprendre :

- toutes les publis utilisant les algos de compression pour les transferts MPI les comparent à LZ (donc type Huffman) parce que ce sont les seuls déjà inclus dans les kernels (suffit de les linker avec -lz) , et dont les temps de compressions sont connus. Et crois moi, là où on fait ce genre de tests (i.e. sur des supercalculateurs, les seuls endroits où on peut espérer saturer l'infiniband), c'est tellement la croix et la bannière pour avoir une malheureuse bibliothèque supplémentaire qu'on fait tout sur ce qui est déjà inclu (enfin, le maximum). Et comme toute publi scientifique qui se respecte, la reproductibilité est de mise, donc sans pré-requis, c'est encore mieux.
Sauf que là tu compares un algo en O(N) avec un O(N log(N)). C'est une méthode de comparaison de base que tout le monde utilise. Fais un peu de biblio sur le sujet, et tu verras...
- une menace... ? Hé bah, 'faut pas grand chose... Faut arrêter d’être parano les gars : relis, il n'y a aucune menace dans ce que j'ai écris. Au lieu de jouer les vierges effarouchées et te défiler, tu dis des trucs faux, je te réponds. Ca te dérange ? Tant pis.
Non, c'est juste que je doute que tu puisse me mettre en défaut sur ce genre de problématique. Et pour le moment, à part des affirmations péremptoires (type "mais non le XOR on ne peut pas le faire sur des réels") montre que tu as beau avoir une bonne culture de ce domaine, n'en reste pas moins que contrairement à ce que tu penses, il y a toujours des choses à apprendre.

- de mon coté je suis parfaitement d'accord avec toi sur un point : je n'arrive pas à lire des pavés, et quand vraiment ils sont longs je lis vos posts en diagonale... Mais ça pour le coup c'est moi avec moi meme.

PS : d'ailleurs la publi n'en n'est sans doute meme pas une, ça doit etre un draft (ni date ni journal). M'étonnerait que les reviewers aient laissé passer une publi où on décrit la méthode de compression et pas de décompression...

@fragmentation: Puisque cette notion d'égalité est celle de l'égalité d'ensembles, parlons d'ensembles. Deux ensembles sont dits égaux s'ils ont les mêmes éléments. L'égalité est ainsi définie, mais elle n'est pas toujours décidable (elle ne l'est même jamais entièrement).

Pour ce qui est des réels, cela n'a de sens de se demander si deux réels a,b sont égaux que si l'on suppose que a et b définis par les propriétés respectives A,B et si tout réel satisfaisant A est égal à tout réel satisfaisant B. Sinon, il manque un contexte, et cela revient à se demander si Jack et Sir Carl sont la même personne avant le début de l'enquête: pas évident en effet.

Les algorithmes réels (au sens de réalité) sont toujours limités en taille car la mémoire est limitée, ils ne peuvent donc pas comparer tous les réels et il s'agit plutôt d'en trouver qui soient efficaces.

Merci de pointer l'erreur dans la démonstration suivante :

---

prop0 : *L'ensemble des programmes est clairement en bijection avec N

Considérons l'ensemble P des programmes qui génèrent des suites infinies de 1 et de 0. Etant donné un programme p de P, appellons exec(p) la suite infinie générée, et exec(p)(n) le bit 0 ou le bit 1 au rang n.


propA : Deux programmes qui génèrent des suites différentes, sont différents.


Enumérons les éléments de P, par une suite S de programmes. Alors on peut associer à chaque élement de la suite, la chaine issue de l'execution du programme

S(0) = p0 -->    exec(S(0))
..
S(n) = Pn -->    exec(S(n))

Alors par diagonalisation, on peut toujours trouver un programme x qui n'est égal à aucun S(n) quelque soit n. Il suffit de considérer le programme qui au rang 0 génère le bit inverse de S(0)(0), au rang 1 génère le bit inverse de S(1)(1) ... au rang n génère le bit inverse de S(n)(n).

Le procédé diagonal stipule que la suite générée par le programme x n'est pas dans la liste des chaines générées par les programmes déjà listés. En application de la propA, le programme x n'est donc l'image d'aucun n par la suite S. Quelque soit n, S(n) != x

L'ensemble des programmes qui générent des suites infinies de 0 et de 1 n'est donc pas dénombrables.
La prop0 affirme qu'ils sont dénombrables (on peut clairement les énumérer, du fait de la définition d'un programme).

Il y a contradiction.

Bon j'ai du faire une fausse manip car ma réponse s'est perdue dans le vide intersidéral, et j'ai pas le courage de la re-pondre. Pour faire rapide, ta suite obtenue par diagonalisation ne peut pas être générée par un programme, sinon contradiction comme tu l'as remarqué.

Par ce genre de raisonnement je crois qu'il est possible d'arriver à une preuve de l'indécidabilité du problème de l'arrêt, du moins il me semble que j'avais vu un truc à ce sujet un jour.

Il y a trois lacunes majeures:
-définition d'un programme qui énumère ls suites (est-ce un objet de la vie réelle, un programme informatique? Si oui, aucun programme d'énumère une suite infinie car la mémoire est toujours finie.)
-preuve claire de la proposition 0
-preuve de la proposition A

Oh oh oh oh en fait en relisant mieux ton truc, je me rend compte que tu es exactement retombé sur ça. Il y a bien une contradiction, et le seul moyen de la lever, c'est de réaliser qu'il n'y a pas moyen de savoir pour ton algorithme diagonal qui génère à l'étape n S(n)(n) de savoir si le programme S(n) va un jour pondre l'élément S(n)(n) ou pas. Donc bravo tu viens de trouver une démonstration du problème de l'arrêt tout seul, c'est pas donné à tout le monde.

paela a écrit: Si oui, aucun programme d'énumère une suite infinie car la mémoire est toujours finie.)

On parle de programmes théoriques qui ont accès à une mémoire non bornée. La théorie des programmes ayant une mémoire finie n'est pas très intéressante : C'est simplement la théorie des automates finis.

paela a écrit: -preuve claire de la proposition 0

Il suffit d'énumérer les programmes par ordre lexicographique. C'est du niveau CE1.

paela a écrit: -preuve de la proposition A

Si f(a) != g(a) alors f != g. Il te faut vraiment une preuve pour ça ?