Je serai plus que reconnaissant si quelqu'un serait en mesure de m'expliquer comment la complexité de Kolmogorov est liée à l'aléatoire, et les entrées aléatoires.Kolmogorov complexité
Une autre chose que je ne peux pas comprendre - nous savons que le calcul de la complexité de Kolmogorov d'une entrée X donnée n'est pas décidable. Compte tenu de cela, comment peut-il être une mesure de l'aléatoire?
grâce
Kolmogorov au hasard est une définition particulière du concept intuitif vague de « aléatoire » - qui d'autre définition faites-vous référence lorsque vous demandez des relations (pour référence http://en.wikipedia.org/wiki/Random_number)?
Je ne suis pas votre schéma de pensée en demandant pourquoi on devrait être capable de déterminer dans le cas général quelles chaînes sont Kolmogorov aléatoire afin que le concept soit bien défini. Pourriez-vous élaborer sur ce qui vous trouble? Si rien d'autre, permettez-moi de vous montrer le problème: le concept d'arrêt du programme est bien défini, même s'il n'y a pas d'algorithme pour déterminer, dans le cas général, si un programme particulier présente la propriété.
Vous devriez penser l'inverse. Si quelque chose n'est pas aléatoire, cela signifie qu'il suit une loi , et cette loi peut donner une description plus simple de l'information. Pensez à zip: au lieu du fichier, vous donnez une procédure pour générer le fichier qui est généralement plus compact que le fichier source. Ceci est possible car le fichier source contenait un certain ordre: si le fichier source était une séquence aléatoire de caractères, aucune compression n'aurait été possible.
Si vous êtes intéressé par ce sujet, je vous recommande fortement "Computability and Randomness" par Andre 'Nies, Oxford Logic Guides n.51.
Merci, la seconde m'a vraiment aidé à fixer un peu mon esprit. Mais je ne comprends toujours pas comment kolmogorov est liée à la caractérisation d'une séquence aléatoire. Est-ce une sorte d'évaluation/mesure? Une chose de plus qui me vient à l'esprit. Si nous ne pouvons pas déterminer si un nombre est vraiment un nombre aléatoire, comment pouvons-nous générer des nombres aléatoires? – RanZilber