Qu'est-ce que l'aléatoire?

Il y a 3 heures, Spontzy a dit :

pour l'histoire des programmes, j'avais lu (mais où ?????) qu'il existe une machine de Turing universelle optimale qui minimise tout programme. Donc que tout programme est optimal, à une constante près. Donc que la complexité de Kolmogorov est définie à une constante près.

 

Oui, tout à fait, mais ici on travaille avec des suites finies, donc la constante prés n'est pas forcément négligeable, par rapport à la taille de la suite.

Bonne soirée.

Il y a 5 heures, Spontzy a dit :

Donc toute suite finie est potentiellement aléatoire (dans le sens est un extrait d'une suite infinie aléatoire). Car toute suite aléatoire infinie doit être nombre univers (c'est mon intuition, je ne connais pas de démonstration). Donc une suite aléatoire ne peut être qu'infinie.

Pardon je n'avais pas vu la suite, et c'est précisément ce que j'expliquai dans mon message juste avant. Donc tu vois bien que cette suite de 64 bits est non aléatoire.

il y a une heure, contrexemple a dit :

Avec ce mode de compression on devrait en venir à bout : https://fr.wikipedia.org/wiki/Compression_de_données#Codage_RLE

Bonsoir,

Pas sûr que ce soit suffisant car il faudrait se mettre d'accord sur l'endroit de la séparation entre le nombre d'occurrences et le bit répété, ce qui me paraît non trivial, pour le moins si nous n'avons que du binaire à disposition (caractères 0 ou 1)!

Personnellement j'aurai plutôt pensé à un algorithme de type Huffmann ou par dictionnaire. Quoiqu'il faille aussi là encore stocker l'arbre ou le dictionnaire correspondant.

Citation

Pardon je n'avais pas vu la suite, et c'est précisément ce que j'expliquai dans mon message juste avant. Donc tu vois bien que cette suite de 64 bits est non aléatoire.

Oui j'ai dit des bêtises.