Comments on Pourquoi e et π paraissent-ils plus aléatoires que génériques ?

Couard Anonyme (2014-07-30T07:15:44Z)

@DM
Ton commentaire a assez peu de lien avec l'entrée de DAM mais puisqu'on s'autorise à digresser chez autrui sans vergogne…

Non seulement les problèmes industriels ne sont pas aléatoires mais en plus nous avons une manière biaisée de les poser.

C'est ainsi que le simplexe dual est significativement plus rapide sur les problèmes industriels que le simplexe primal alors qu'ils ont image en miroir l'un de l'autre. L'explication est que nous posons la plupart de nos problèmes sous forme de minimisation du coût et non de par exemple de maximisation de la productivité (ou du dual du coût).

Ptitboul (2014-07-29T09:14:59Z)

Mon intuition c'est que π ou e sont des nombres naturels dans les mathématiques continues (géométrie / analyse). Et que la notion de nombre générique ne vit pas dans ce type de mathématiques. Donc ça serait surprenant qu'ils soient pseudo-génériques, alors que ça ne surprend pas qu'ils soient pseudo-aléatoires.
Ce qui est cohérent avec ta remarque sur l'inexistence de nombres «naturels» pseudo-génériques, car les nombres «naturels» sont ceux issus des mathématiques continues. Les nombres construits par arguments de diagonalisation, par exemple, sont issus des mathématiques discrètes (en premier lieu la logique), non ?

DM (2014-07-25T18:00:37Z)

Au Vienna Summer of Logic, il y a eu un panel où l'on se posait (au fond) la question suivante: les solveurs ont un comportement très différent sur les instances SAT que l'on veut résoudre effectivement pour prouver la correction de circuits ou de logiciels et sur les instances aléatoires (pour la distribution la plus évidente sur 3SAT), on sait en partie pourquoi et quand les instances aléatoires sont dures mais en revanche on ne sait pas pourquoi les instances « industrielles » ne sont pas si dures que cela.

On s'en tire par un argument « elles découlent d'objets conçus par des humains, qui ont donc certaines régularités », mais ce n'est guère satisfaisant.

Ruxor (2014-07-24T20:48:54Z)

@f3et: Il y a des constructions explicites, oui (enfin, explicites… en utilisant l'oracle de l'arrêt), par des sortes de diagonalisations (en gros, on énumère les fermés d'intérieur vide calculables et on fait ce qu'il faut pour les éviter), qu'on peut aussi appliquer pour fabriquer des réels aléatoires : ça doit être expliqué dans le livre de Cooper ou celui de Lerman que j'ai cités ; mais je n'en connais pas qui ait de définition aussi simple que la constante de Chaitin. Pour les pseudogénériques, c'est encore plus mystérieux, et c'est un peu la question que je pose : je ne sais pas du tout comment on en fabriquerait (autrement qu'avec le même procédé ; on peut peut-être se limiter à une diagonalisation sur les primitifs récursifs, ce qui rendrait la construction théoriquement calculable, mais je ne sais vraiment pas faire un générateur pseudogénérique aussi facilement qu'un pseudoaléatoire).

f3et (2014-07-24T19:54:09Z)

Il est assez difficile de construire des nombres aléatoires, mais la constante de Chaitin (Omega) en est un. A-t-on une construction d'un réel générique? Ou, à défaut, d'un réel pseudo-générique ?

Ruxor (2014-07-24T13:52:20Z)

@jonas: Ooops, of course you're right. Fixed.

Frank Wolff (2014-07-24T12:33:04Z)

@YBM
C'est-à-dire que π contient la Bibliothèque de Babel.
Quand je pense que la Bibliothèque de Babel contient π…

jonas (2014-07-24T09:05:05Z)

This sentence looks like a mistake to me: "pour trouver $n^2$ bits 0 consécutifs dans une suite aléatoire, il faudra aller jusqu'au bit $n^2$ environ". It actually takes about $2^{n^2}$ bits to find such an infix.

YBM (2014-07-23T20:21:28Z)

Le caractère normal de π a donné l'idée à un développeur assez chafouin d'une implémentation assez originale d'un système de fichier :

https://github.com/philipl/pifs

(don't do this at home ! En voulant sauvegarder un fichier de deux ou trois mots avec vi, je n'ai jamais pu redémarrer mon système sinon brutalement)

Ted (2014-07-23T11:15:54Z)

Article fascinant, merci beaucoup ! Ayant passé du temps à étudier les propriétés des réels aléatoires mais ne connaissant pas la notion duale présentée ici, j'ai appris tout un tas de choses vraiment passionnantes =)


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 9b284c


Recent comments