16 novembre 2011

12 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • Le problème 3n+1 : cycles de longueur 5 (II)

    le 25 mai 2020 à 15:40, par pierre simonnet

    C’est vrai que c’est joli.
    l’enoncé est il accessible aux enfants de 8 ans ? Je pense que oui.
    ce que je trouve amusant c’est que grâce à la théorie des automates finis, on peut montrer que pour un k fixé, on peut prouver que l’existence d’un cycle de longueur inférieur ou égal à k, autre que le cycle trivial de longueur 3, est un problème décidable. Malheureusement comme il s’agit de composer un petit transducteur en base 2, de 7 états ( k-1) fois avec lui même, on se retrouve à tester
    le vide sur un automate à 7^k états. Shalom à de l’avance sur un programme éventuel.

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.