Liste d'entiers "logiques"

Quentino37
Quentino37
dans Fondements et Logique
Je me suis posée cette question : peut-on "reconnaître" une liste d'entiers infinie logique
Ce n'est pas très facile à expliquer et sans doute que ma "définition" d'une liste d'entiers logique n'est pas bonne et on peut l'améliorer :-)
Ça doit être une liste d'entiers, constructibles (on peut déterminer chaque terme en un temps fini), et pas de hasard.
Je suis sûr qu'on peut ajouter des trucs à ma def car elle n'est pas rigoureuse.
J'entend par reconnaître, le fait de savoir si la suite est logique ou pas (on peut faire un test sur tout les nombres de la liste infinie par exemple). Mais ce n'est toujours pas rigoureux.

Je vais partir en vacances demain matin je ne sais pas à quelle heure donc je risque de ne pas pouvoir voir vos messages (peut-être grâce au tel je pourrai répondre) mais pendant mes vacances à la montagne de deux semaines et demi je vais pouvoir réfléchir un peu plus pour approfondir la question.

PS : par exemple l'ensemble des nombres premiers est "logique".
Je suis donc je pense 

Réponses

  • Dom
    Dom
    Toute suite est « logique » il me semble.
  • Quentino37
    Quentino37
    Si on prend une suite que l'on défini comme ça :
    élément 1: nombre aléa entre 1 et 1
    élément 2: nombre aléa entre 1 et 2
    élément 3: nombre aléa entre 1 et 3
    ...
    élément n: nombre aléa entre 1 et n
    ...

    Elle n'est pas logique

    En revanche, la série $u(n)$ = partie entière de $10^n \pi -10\times$ partie entière de $10^{n-1} \pi$ est logique (si on remplace $\pi$ par la somme des $n$ premiers termes de la formule donnant 8 décimales de $\pi$ par terme de Srinivasa Ramanujan par exemple).

    Je pense que l'on pourrait poser la question à l'envers : comment identifier une liste de nombres infinie générée avec du hasard.
    Je suis donc je pense 
  • Dom
    Dom
    Bon c’est bien d’avoir pris $\pi$.
    À une suite, j’associe un réel et je le note $\ell$.
    Puis je construis comme tu l’as fait une suite logique qui tend vers $\ell$.
  • Médiat
    Médiat
    Voir les définition de Löf-Martin; ou de Levin/Chaitin ou de Schnorr

    Lire aussi le document de Jean Paul Delahaye : "Le concept de suite aléatoire et la thèse de Church "
  • Quentino37
    Quentino37
    Dom: voila comment je m'y prends pour $\pi$. On à $\displaystyle u(n)=\lfloor 10^n \frac{1}{\displaystyle \sum_{k=0}^{n} \frac{(4n)!}{n!^4} \frac{1103+26390n}{(4×99)^ {4n}}} \rfloor -10\lfloor 10^{n-1} \frac{1}{\displaystyle \sum_{k=0}^{n} \frac{(4n)!}{n!^4} \frac{1103+26390n}{(4×99)^ {4n}}} \rfloor$

    PS : le temps que je recopie la formule vous avez écrit des messages.
    Je suis donc je pense 
  • Quentino37
    Quentino37
    Merci Médiat :)
    Je suis donc je pense 
  • Philippe Malot
    Philippe Malot
    Bonsoir,
    Avant d'aller plus loin, il faut justement donner une définition rigoureuse d'une suite d'entiers logique.
    Que signifient "on peut déterminer chaque terme en un temps fini" et "pas de hasard", si $(u_n)$ est une telle suite ?
  • Quentino37
    Quentino37
    Nouvelle définition plus rigoureuse:
    Si on à la technique pour créer la suite, la technique doit avoir une "taille" finie, et si deux personnes utilisent la technique séparément ils obtiendront la même suite.(j'essaye d’approfondir...)
    Je suis donc je pense 
  • christophe c
    christophe c
    Ca porte un nom, ça s'appelle "suites d'entiers" qui est récursive
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Quentino37
    Quentino37
    merci christophe c :]
    Je suis donc je pense 
  • christophe c
    christophe c
    Synonymes : "calculable" ; "décidable", mais à ne pas utiliser car sont des termes un peu maladroits.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Georges Abitbol
    Georges Abitbol
    @Quentino37 : C'est une bonne remarque d'avoir remarqué que c'est pour les suites infinies que c'est pertinent :) !

    Pour t'amuser un peu, en reprenant tes termes : soit une technique qui permet de produire une "liste de listes logiques". Que dire de la liste, qui, en tout rang $n$, contient le nombre $m+1$, où $m$ est le $n$-ème nombre de la $n$-ème liste produite par ta technique ? Qu'en conclure ?
  • Quentino37
    Quentino37
    la liste "qui en tout rang n, contient le nombre m+1, où m est le n-ème nombre de la n-ème liste produite par ta technique" est logique si et seulement si si la technique utilisé est "logique"? :)
    Je suis donc je pense 
  • Quentino37
    Quentino37
    J'ai barré si et seulement si car on peut créer un contre exemple.
    Si $n=k,\space U_{n}(k)=1,$
    Sinon$,\ U_{n}(k)=nb \space aléa(1,n) \times k$

    Comme ça l'ensemble des $U_{n}(n)_{n\in \mathbb{N}} +1$ ne sont que des $2$ donc une suite logique
    Je suis donc je pense 
  • raoul.S
    raoul.S
    https://fr.wikipedia.org/wiki/Ensemble_récursif
  • Georges Abitbol
    Georges Abitbol
    @Quentino37 : Opopop ! Attends avant de continuer avec tes "aléa", "aléa". Ca serait bien que tu te poses des questions sur ce que ça veut dire :) !

    Et pour "mon énigme", je suppose que la technique utilisée pour produire la liste de listes est "logique", oui, même si on t'a dit qu'il faut plutôt appeler ça autrement.
    En tout cas, vue la définition de la liste que je donne ($m+1$ blablabla) c'est clair qu'elle est "logique", n'est-ce pas ?
  • Quentino37
    Quentino37
    oui c'est logique le fait que ce soit récursif

    PS: nb aléa c'était une abreviation pour nombre aléatoire entre un nombre et un autre(entier) (et de telle façon que l'on à autant de chance de tomber sur chaque nombre de l'intervalle)
    Je suis donc je pense 
  • Georges Abitbol
    Georges Abitbol
    @Quentin37 : Ben oui, justement. C'est quoi, un nombre "aléatoire" ?
  • Quentino37
    Quentino37
    Pour moi c'est un nombre que l'on obtient tel que l'on ne peut pas savoir à l'avance le résultat cependant on peut le décrire grâce à la probabilité que ça tombe sur un intervalle
    (On gagne forcément de l'information.)
    Je suis donc je pense 
  • Poirot
    Poirot
    C'est ce qu'on appelle une variable aléatoire réelle en général.
  • Quentino37
    Quentino37
    Merci Poirot :)
    Je vais aller dormir(car en théorie je suis sensée dort...)

    (j'essayerai de voir si je pourrai utiliser mon tel pour aller sur le forum quand je serai à la montagne :)
    Au revoir !!!
    Je suis donc je pense 
  • Georges Abitbol
    Georges Abitbol
    @Poirot : Ben, justement, non. Une variable aléatoire réelle n'est pas du tout "un nombre que l'on obtient tel que l'on ne peut pas savoir à l'avance le résultat cependant on peut le décrire grâce à la probabilité que ça tombe sur un intervalle", c'est une fonction !

    @Quentin : Le "résultat" de quoi ? Ca veut dire quoi, "gagner de l'information" ?
  • gerard0
    gerard0
    Bonjour Georges Abitbol.

    C'est vrai qu'une VA est une fonction, mais qui sert justement à manipuler des "nombres que l'on obtient tel que l'on ne peut pas savoir à l'avance le résultat cependant on peut le décrire grâce à la probabilité que ça tombe sur un intervalle". Ces nombres qu'on appelle les réalisations de la variable aléatoire. Donc la réponse de Poirot est logique !
    Et l'étude des suites aléatoires s'intéresse justement aux réalisations des suites de VA.

    Cordialement
  • gerard0
    gerard0
    Quentino37, ce que tu veux est que ta suite soit déterministe ("si deux personnes utilisent la technique séparément ils obtiendront la même suite").

    Cordialement.
  • Georges Abitbol
    Georges Abitbol
    @Quentin (qui ne sait peut-être pas), gerard0 (qui sait) : La théorie mathématique des probabilités ne parle pas de hasard ; elle se contente de décrire certaines parties de l'ensemble des suites en leur donnant une "taille", une "mesure". Mais ça n'a rien à voir avec le hasard !

    @gerard0 : Quentin avait plutôt l'air de s'intéresser aux suites produites par des algorithmes !
  • gerard0
    gerard0
    Effectivement.

    Mais tu es quand même un peu rude avec la théorie des probabilités, qui s'intéresse bien à une forme de hasard ("le hasard réglé") avec des outils parfaitement déterminés. Et efficaces !

    Cordialement.
  • Georges Abitbol
    Georges Abitbol
    @gerard0 : En fait, je crois que j'ai commencé à "comprendre les probas" (je veux dire par là, savoir résoudre des exercices, etc) quand j'ai compris que c'était un "hasard réglé", comme tu dis. Ca a été un déclic ! Et quand je vois le nombre de bêtises philosophiques sur le "hasard" par des gens sérieux, des erreurs de matheux professionnels sur les statistiques, je me dis que revenir au noyau dur et se souvenir que les probas ne sont qu'un calcul de proportions, ça permet d'avoir les pieds sur terre et de savoir de quoi on parle.

    En tout cas, je voulais prévenir Quentin qui (je crois) n'a pas encore subi l'enseignement des probas au lycée et qui a l'esprit encore vierge là-dessus !
  • gerard0
    gerard0
    Effectivement !

    Quand on "prend un .. au hasard", si la règle de probabilité du "hasard" n'est pas donné, on ne sait pas ce qu'on fait. Cette expression est apparue historiquement pour parler d'équiprobabilité (le "dé parfait", le tirage de boules indiscernables au toucher, ...), au troisième millénaire il est temps de dire "de façon équiprobable" ou de donner la règle d'obtention.

    Cordialement.
  • Quentino37
    Quentino37
    @George Abitole J'entends par gagner de l'information que avec les données actuelles de notre système on ne puisse obtenir cette information.
    Je suis donc je pense 
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 7

7 Invités