Comment construire une suite finie aléatoire?

Il y a 3 heures, azad2B a dit :

Amusez vous bien. Et pardonnez mon erreur. Merci.

On fait tous des erreurs, le tout c'est de les reconnaître.

Cordialement.

Il y a 4 heures, contrexemple a dit :

Pour un langage fixé, et une suite finie, le problème de savoir si cette suite est aléatoire ou non, est un problème calculable.

En effet il suffit d'énumérer tous les programmes possibles de tailles strictement plus petit que la suite (il y en a un nombre fini) et regarder s'il y en a qui génére la suite, si oui, elle n'est pas aléatoire, sinon elle est aléatoire.

Je pense oui qu'on peut énumérer de tels programmes pour une longueur finie mais pour vérifier si ils génèreraient la suite, comment pourrait-on être sûrs pour un mot x que ces programmes de longueur inférieure ou égale à |x| (et générés automatiquement) s'arrêtent?  

Nous savons déjà que certains ne s'arrêteront pas : par exemple ceux qui contiennent en C une boucle while(true){}.

Il y a 4 heures, contrexemple a dit :

Mais non, la complexité est définie à constante prés à cause du langage utilisé, il suffit que ta suite soit une constante du langage pour que la complexité avec ce langage soit basse, alors que pour un autre langage il pourrait en être autrement.

Pour résoudre cela, il faudrait fixé arbitrairement un langage à utiliser pour calculer la complexité...

Intéressant, connais-tu le rapport mathématique entre ce langage et la valeur de la constante c?

De plus il semblerait que c doive être supérieur ou égal à 1, mais je n'en suis pas absolument certain.

Il y a 3 heures, azad2B a dit :

Salut.
Je m’aperçois que je m’étais trompé sur le sens profond de la question posée.
Et c’est le mot « compression » utilisé, et que j’avais cru reconnaître comme étant un rapport entre la taille d’un fichier compressé et celle du fichier original, qui a provoqué mon erreur.
Votre discussion semble plus axée sur les critères permettants de d’affirmer qu’ une suite présente les caractères irréfutables d’un tirage aléatoire pur.
Cette discussion, implique donc la connaissance de techniques que je ne connais absolument pas et je vous prie de m’excuser de mon erreur et de mon intrusion dans le débat.
Amusez vous bien. Et pardonnez mon erreur. Merci.

Aucun soucis, tu as tout de même respecté le sujet ce serait dur de te faire le moindre reproche

il y a 1 minute, Quasi-Modo a dit :

1/Je pense oui qu'on peut énumérer de tels programmes pour une longueur finie mais pour vérifier si ils génèreraient la suite, comment pourrait-on être sûrs pour un mot x que ces programmes de longueur inférieure ou égale à |x| (et générés automatiquement) s'arrêtent?  

Nous savons déjà que certains ne s'arrêteront pas : par exemple ceux qui contiennent en C une boucle while(true){}.

2/Intéressant, connais-tu le rapport mathématique entre ce langage et la valeur de la constante c?

De plus il semblerait que c doive être supérieur ou égal à 1, mais je n'en suis pas absolument certain.

1/Oui, c'est exact, mais pour le coup, on peut n'utiliser que des programmes qui s'arrêtent, sans "while" que des boucles "for" (un langage récursif primitif), cela sera déjà pas mal.

2/La constante c, c'est le coût de traduction d'un langage vers un autre, c'est tout.

Tiens un lien qu'il me semble je t'avais déjà donné :

il y a 53 minutes, contrexemple a dit :

1/Oui, c'est exact, mais pour le coup, on peut n'utiliser que des programmes qui s'arrêtent, sans "while" que des boucles "for" (un langage récursif primitif), cela sera déjà pas mal.

2/La constante c, c'est le coût de traduction d'un langage vers un autre, c'est tout.

1/ Excellente idée, mais si les programmes sont bien générés aléatoirement, comment être certains que le compteur de la boucle for n'est pas redéfini dans ladite boucle à une valeur inférieure?

Par exemple for(int i=0; i<10; i++){ i=2; }

2/ Parlons-nous bien du c pour lequel l'incompressibilité est définie? A savoir c tel que K(x) < |x| - c ?

il y a 2 minutes, Quasi-Modo a dit :

2/ Parlons-nous bien du c pour lequel l'incompressibilité est définie? A savoir c tel que K(x) < |x| - c ?

Regarde la vidéo, tout y est détaillé, je ne sais rien de plus que ce qu'il y a dans cette vidéo.

il y a 5 minutes, Quasi-Modo a dit :

1/ Excellente idée, mais si les programmes sont bien générés aléatoirement, comment être certains que le compteur de la boucle for n'est pas redéfini dans ladite boucle à une valeur inférieure?

Cela n'est pas trés difficile, tu peux programmer un analyseur synthaxique qui va te dire, si le compteur de boucle n'est pas changer au cours de la boucle, ce qui reviendrait à faire un while.

Ou bien, plus simplement on peut se restreindre à un langage récursif primitif.

il y a 3 minutes, contrexemple a dit :

Ou bien, plus simplement on peut se restreindre à un langage récursif primitif.

Après ce ne sera donc pas un langage Turing-complet c'est dommage

D'ailleurs je me demande si la complexité de Kolmogorov est bien définie sur des langages non turing-complets? 

Mais bon dans le fond pourquoi pas? Je regarderai ta vidéo au plus tôt

il y a 2 minutes, Quasi-Modo a dit :

D'ailleurs je me demande si la complexité de Kolmogorov est bien définie sur des langages non turing-complets? 

Oui, mais alors tu peux plus appelé cela la compléxité de Kolmogorov.

il y a 24 minutes, contrexemple a dit :

Oui, mais alors tu peux plus appelé cela la compléxité de Kolmogorov.

C'est bien ce qu'il me semblait

Décidément, l'aléatoire au sens de Kolmogorov pour une suite finie restera un mystère pour moi

Bonne soirée

Sinon je viens de penser à autre chose : un compilateur peut-il détecter (sans doute que non dans tous les cas) qu'une boucle while ne s'arrête pas? Par exemple while(true){} serait facile à détecter par un compilateur. En effet, cela reviendrait à résoudre le problème de l'arrêt dans tous les cas, ce qui est impossible, non?

Toutefois il faudrait pouvoir refuser tous les programmes dont la condition C du while est vraie avant l'arrivée dans la boucle, et dont la condition C ne peut pas redevenir fausse par le code situé dans la boucle. Dans un programme déterministe, c'est tout à fait plausible, non?

il y a 7 minutes, Quasi-Modo a dit :

Toutefois il faudrait pouvoir refuser tous les programmes dont la condition C du while est vraie avant l'arrivée dans la boucle, et dont la condition C ne peut pas redevenir fausse par le code situé dans la boucle. Dans un programme déterministe, c'est tout à fait plausible, non?

Non en fait ma première idée était plus juste, ça n'est pas possible de détecter les boucles while infinies dans tous les cas, car cela revient effectivement à résoudre le problème de l'arrêt (démontré comme irrésoluble). J'ai donc rien dit

il y a 9 minutes, Quasi-Modo a dit :

Sinon je viens de penser à autre chose : un compilateur peut-il détecter (sans doute que non dans tous les cas) qu'une boucle while ne s'arrête pas? Par exemple while(true){} serait facile à détecter par un compilateur. En effet, cela reviendrait à résoudre le problème de l'arrêt dans tous les cas, ce qui est impossible, non?

Toutefois il faudrait pouvoir refuser tous les programmes dont la condition C du while est vraie avant l'arrivée dans la boucle, et dont la condition C ne peut pas redevenir fausse par le code situé dans la boucle. Dans un programme déterministe, c'est tout à fait plausible, non?

Il suffit d'utiliser un compteur de boucle spécifique pour le for et le problème est réglé.

Regarde la vidéo il utilise un bon vieux compresseur de donnée, et cela suffit pour avoir des résultats impressionnant Delahaye, a fait ce travail, cherche des vidéos de lui, elles sont également trés bien.

Tiens par exemple celle là :

il y a 2 minutes, contrexemple a dit :

Il suffit d'utiliser un compteur de boucle spécifique pour le for et le problème est réglé.

Regarde la vidéo il utilise un bon vieux compressuer de donnée, et cela suffit pour avoir des résultats impressionnant Delahye, a fait ce travail, cherche des vidéos de lui, elles sont également trés bien.

Oui tu as raison, question de pragmatisme, mais comme dit, les langages récursifs primitifs sont non-turing complets et la complexité de Kolmogorov semble donc ne pas les concerner. J'ai regardé la première demi heure de la vidéo que tu as postée, c'est vrai qu'il explique de façon sympa. Merci pour le tuyau

En outre je suis tombé sur des articles qui prétendent que la complexité de Kolmogorov peut être estimée par le calcul de l'entropie de Shannon, et beaucoup semblent souligner les similitudes entre les deux méthodes. L'entropie de Shannon est calculable par contre, du coup ça me paraît assez étonnant.

Il existe une autre notion de complexité, la profondeur de Bennett