J'ai été choqué par la fin abrupte de cette vidéo !! Pour moi le paradoxe résidait dans le fait que le fameux algorithme du suprême fasciste était dans la liste des lapins mais que puisque l'algorithme donne toujours l'inverse de la prédiction, alors le lapin est indécis sur le choix qu'il ferait car si il dit une couleur l'algorithme donnera forcément la couleur inverse mais il le sait puisqu'il connait l'algorithme. J'avais donc trouvé que les lapins sont voués à perdre mais pas pour la bonne raison ^^
De même. Car la temporalité n’était pas prise en compte par les Lapins et le Fasciste pouvait gagner sur les coups suivants. Ce paradoxe n'est pas solide dans le sens où il n'y a pas qu'une seule réponse... Mais en fait si, car la stratégie des Lapins n'est même pas applicable. Donc, nous arrêtons le raisonnement à cette étape, avant même de passer au tour du Fasciste. CQFD.
Moi j'ai un petit problème avec l'algorithme du Suprême Fasciste : il est impossible de faire une prédiction sur un algorithme qui ne se finit pas. Donc il sera bloqué avant les lapins pour choisir une couleur, donc il ne pourra jamais coiffer une infinité de lapins, donc nous sommes en face d'un pat mathématiques, non ?
C'est tout à fait vrai ! En revanche, il est précisé dans l'énoncé que le suprême fasciste ne peut que faire des calculs que les machines de Turing savent faire. Or, une machine de Turing ne sait pas "utiliser du hasard". Donc le suprême ne peut pas lui non plus faire usage de hasard pour déterminer la couleur du chapeau duquel il coiffe un lapin.
@@tristannemoz7277 meme avec un ordinateur quantique? il me semble qu'Alain Aspect explique qu'ils ont des random calculator number quantique deuisdes décénie ;)
@@myfreedom42 un ordinateur de quantique n'est pas une machine de turing. Une machine est dite de turing lorsqu'il y a un bijection entre cette machine et une machine a ruban de turing
Bah en soi une pièce ne sera jamais " parfaite " donc il sera toujours possible de réaliser une algorithme de (machine learning par exemple) capable de prédire les prochains lancer de piècesen fonction des lancers précédents
Merci Lê d'aborder des problème de fond comme ça. Mon lapin a lui même été tué par un suprême-fachiste qui voulait lui mettre un chapeau, maintenant sa voix est entendue
Bonjour, est-ce qu'il serait possible d'avoir la référence vers le papier de Chiffaudel qui y fait référence ? En particulier, il est possible que mon raisonnement soit erroné, mais il me semble qu'ici tu as juste montré qu'il n'est pas possible de les ordonner par taille. On pourrait très bien les ordonner autrement. Par exemple, on pourrait les énumérer de la façon suivante : Machines de Turing à n états qui s’arrête en n étapes ou moins. Alors dans ce cas, le problème de l'arrêt n'est plus obstacle puisqu'il sera impossible de dire si la machine n'a pas encore été énumérée par qu'elle ne termine pas, ou si c'est parce que la longueur de son exécution n'a pas encore été atteinte.
C'est le même argument que la diagonale de Cantor sur les nombre reels calculables? Ils sont "listables" (denombrables) car correspondant a un algorithme. On pourrait faire un algorithme diagonal qui change un chiffre pour chacun dans la liste. le nouveau nombre est calculable par cet algorithme mais n'est pas dans la liste.
Mais si un des algorithmes lapins ne se termine jamais et qu'on attend jusqu'à la nuit des temps... Du coup ils ne peuvent plus fairfe d'erreurs, donc pas d'infinité d'erreurs, donc ils ont gagné quand même ^_^ ?
le probleme reside dans le fait que l'infini se contient lui meme, après une infinité de temps (ce qui n'est normalement pas faisable car l'infini n'est pas un nombre), les algorithmes n'auront toujours pas finit car ce meme temps infini est contenu dans le temps de calcul des algorithmes (voilà pourquoi les raisonnements de type "en fin de compte" ne marchent pas, il n'y a pas de fin et les raisonnements ensemblistes ne s'appliquent pas)
@@serious-goober D'après le définition du problème, peu importe que ça finisse. Si un des algo bloque, et ce sera le cas, alors ils cesseront de faire des erreurs, et donc il y en aura une quantité finie : Les lapins ne peuvent plus jouer, et donc ne peuvent pas perdre (càd continuer de faire des mauvaises prédictions), or c'est tout ce qu'on leur demande (pas de gagner, càd faire uniquement des bonnes prédictions à partir d'un certain rang) Donc je pense qu'il a raison !
J'ai eu le même raisonnement, les lapins ne feront pas une infinité d'erreur... Il ne perdront jamais. Même si ils ne gagnent pas pour autant. Match nul ?
@@aaronaaron5013 moi, pas du tout. Mais pour lui, oui je suis pressé. Il faut prendre des vacances vite et longue. Il y a déjà 300 commentaires sur la vidéo. Je sais pas combien de temps on peut passer sur une chaise longue le temps de lire sa. En tout cas encore bravo pour les vidéos
@@vivelavie858 loool non je plaisante c'est juste que ça m'as fais sourir ton commentaire genre "bonjour, merci, bonne vacance" 😂😂 comme si tu étais entrain de courir et que tu t arreter 3 secondes pour dire ça et repartir looooool
8:08 : Le changement d'algorithme est aussi un algorithme. (et récursivement, un algorithme de changement d'algorithme de changement d'algorithme est un algorithme, donc est dans la liste) édit : bon, donc en fait, les 2 arguments étaient mauvais.
J'ai une vrai question, pourquoi le terme de "suprême fasciste" est utilisé dans certains problèmes de maths que présente science4all (dans sa vidéo sur l'axiome du choix c'est le cas également il me semble), je me doute que c'est surement ceux qui ont conçu ces problèmes qui ont utilisés ces termes mais je me demande sincèrement pourquoi ? (c'est une histoire de private joke de matheux ?)
Bonjour Lê, Je dois dire que ce problème me perturbe depuis quelques jours. Si j'ai bien compris, le fasciste choisie une fonction allant des entiers vers l'ensemble {noir;blanc} (quand je parle de fonction je parle de quelque chose d'équivalent à une lambda). L'algorithme implémentant cette fonction doit s'arrêter pour tout entier. L'ensemble des fonctions prenant en entré un entier et s'arrêtant pour tout entier ne peut être construit algorithmiquement à cause du problème de l'arrêt. Par contre l'ensemble des fonctions prenant en entré un entier lui peut être construit et il est possible de lui trouver un ordre total. Il est donc possible d'associer un entier à une fonction, et un couple d'entier peut représenter une fonction et l'argument à évaluer. La stratégie des lapins consistait à évaluer séquentiellement chaque fonctions qui s'arrêtent avec différents arguments. Avec l'ensemble que je propose ce serait une mauvaise idée de faire la même chose puisque parmi les fonctions de mon ensemble certaines ne vont pas s'arrêter avec certains arguments. L'idée serai donc d'explorer de plus en plus profondément chacune des fonctions de mon ensemble. Pour cela je peut passer par un interpréteur qui prend deux argument arg1:un entier représentant la fonction arg2:le nombre d'instruction/étape que je souhaite réalisé. l'interpréteur donne en sortie une liste. Les élément de la liste de retour représentent les retours de la fonction arg1. Cet interpréteur est un peu spécial puisque il attribue lui même les entrés de la fonction qu'il interprète. l'interpréteur initialise la liste de sortie avec une liste vide L'interpréteur commence par interpréter la fonction arg1 avec 0 il effectue k1 opération et arg1 s'arrête l'interpréteur ajoute le retour de arg1(0) à la liste de sortie L'interpréteur commence par interpréter la fonction arg1 avec 1 il effectue k2 opération et arg1 s'arrête l'interpréteur ajoute le retour de arg1(1) à la liste de sortie L'interpréteur commence par interpréter la fonction arg1 avec 2 il effectue k3 opération et arg1 s'arrête l'interpréteur ajoute le retour de arg1(2) à la liste de sortie ... L'interpréteur commence par interpréter la fonction arg1 avec n il effectue kn opérations et k1+k2+...+kn=arg2 l'interpréteur renvoie la liste de sortie Dés lors je propose comme stratégie pour les lapins: solution_trouvé := Faux la_meilleur_fonction := 0 iteration := 1 tant que non(solution_trouvé) faire: f:=0 tant que non(solution_trouvé) et f
Avec un coup de diagonale de cantor on peut pas montrer que l'ensemble des suites de chapeaux possible est indenombrable ? Et du coup les lapins ne peuvent même pas mettre en place leur stratégie ? Quelqu'un peut il m'éclairer si je fais une erreur ? (Je pense a l'épisode de s4all sur la diagonale de cantor justement)
Il me semble qu'on s'intéresse uniquement aux suites de chapeaux calculables ici puisque le suprême faciste comme les lapins génèrent les suites algorithmiquement
Fortran de retour! Enfin, une partie de mes études pourrait servir. (Ben oui, je ne suis pas né de la dernière pluie, ni de l'avant-dernière d'ailleurs.) :-)))
Les lapins n'ont pas besoin de savoir si un algorithme termine mais uniquement si il termine aussi vite que celui du suprême fasciste. Ainsi, dès que l’exécution d'un algorithme de la liste des lapins prend plus de temps que l'attribution du chapeau, il est tracé et on passe au suivant.
@Iannis Toussaint On parle de "simples" machines de Turing, il n'y a pas de raison que le même algorithme puisse avoir plusieurs temps d'exécution (l'aléatoire "pur" n'est pas autorisé). Le temps étant relatif au nombre d'étapes de l'algorithme. Et effectivement, comme le dit Paul Amblard, l'algorithme 3 sera dans la liste. Si on admet qu'on peut faire "attendre" un algorithme, c'est qu'une instruction nous permet de le faire, toutes les "attentes possibles" sont donc listées, comme le seraient d'autres instructions. L'algorithme 3 de votre exemple est donc bien distinct du 1.
Rien à voir avec le fond mais les sous-titre en français autogénérés par youtube affiche « La thèse de flirt sur ring » pour « la thèse de Church Turing ». Entre autre variations de transcription des noms (parfois les mêmes de manière différentes). C’est mignon.
Vous pouvez imaginer l'algorithme suivant. Prenez n'importe quelle conjecture non résolue (Riemann, Syracuse, Goldbach, nombres premier jumeau), puis cherchez un contre exemple et essayant toutes les possibilités. L’algorithme s'arrête quand vous trouvez un contre-exemple. Mais si l’algorithme ne s'arrête pas, vous ne pouvez pas savoir si c'est parce qu'il n'existe aucun contre-exemple, ou si c'est parce que celui-ci est tellement grand que vous ne l'avez pas encore trouvé.
10:22 "il est algorithmiquement impossible de construire une liste de tous les algorithmes qui terminent toujours". Il me semble que c'est possible justement, car si j'en crois Wikipédia (source : fr.wikipedia.org/wiki/R%C3%A9cursivement_%C3%A9num%C3%A9rable), "l'ensemble des programmes informatiques qui s'arrêtent est un ensemble récursivement énumérable". Du coup, même si l'arrêt est certes incalculable (on ne peut pas prédire si un algo donné va s'arrêter), j'ai l'impression que ce n'est pas grave pour les lapins, qui ont simplement besoin de la propriété "récursivement énumérable" car elle leur permet de lister, via un algorithme, tous les algorithmes qui s'arrêtent toujours (et donc utilitables par le super-fasciste), jusqu'à trouver en trouver un qui corresponde aux données précédemment acquises. Du coup j'ai l'impression que contre-argument contre les lapins est faux, mais je serais ravi de comprendre en quoi je me trompe si c'est le cas.
Je ne suis pas du domaine mais voici ma compréhension. Les programmes qui terminent et ne prennent pas d'argument sont effectivement récursivement énumérables, avec une astuce. L'astuce est de générer la liste de la façon suivante: tester tous les programmes de longueur au plus N, mais en les laissant tourner au maximum N étapes. Si un programme s'arrête avant N étapes, l'ajouter à la liste, si il prend plus que N étapes on l'arrête et on passe au programme suivant. Puis quand on a fini de tester tous ces programmes, incrémenter N, et on recommence tout cette fois pour N+1. Continuer pour N de 0 à l'infini. Eventuellement, tous les programmes qui terminent finiront par être listés (à l'étape max(L,T) où L est la longueur du programme et T son temps d'exécution). La subtilité est que le programme du diable prend un argument, disons i, qui est l'indice du lapin actuel. Or, l'ensemble des programmes qui prennent un argument i, et terminent pour toute valeur de i, ne semble pas être récursivement énumérable. Je n'ai pas de source pour cette affirmation, mais il y a deux choses qui me font penser que c'est le cas. Premièrement, on voit que la méthode précédente ne marche plus du tout si il y a un argument (même si on se mettait à tester tous les arguments jusqu'à N - les programmes pourraient terminer en un nombre d'étapes variable dépendant de l'argument), or c'est la preuve que j'ai trouvée en cherchant l'affirmation Vikipédia, j'en déduis donc que Wikipédia part du principe que les programmes sont sans argument, et donc que les programmes avec argument sont de nature différente. Deuxièmement, j'ai trouvé sur Stack Exchange une preuve que l'ensemble des combinaisons { P, i : P programme prenant un argument, i argument } telles que P(i) termine, est récursivement énumérable. Autrement dit, on peut lister les programmes qui terminent pour une valeur de l'argument fixé. J'en déduis donc qu'il n'est pas possible de le faire pour tout i, sinon l'énoncé aurait pu être simplifié en enlevant i. Donc en résumé, on peut faire la liste des programmes du diable qui prédiront le chapeau d'un lapin i donné, mais cette liste n'est valable que pour ce lapin. A chaque lapin, on obtiendra une autre liste, ce qui rend impossible la solution pro-lapin.
@@SaiphxXx En effet c'est un bon point, je n'avais pas pensé au problème des arguments. PS je suis contente que quelqu’un ait lu mon argument ! Je ne m'attendais pas à une réponse des années après ! Merci !
Est-ce qu'on ne peut pas utiliser un argument type diagonale de Cantor pour réfuter l'argument pro-Lapin ? Ne peut-on pas parler d'un algorithme qui diffère du premier algorithme à sa première sortie, du second à sa seconde sortie etc. Ce qui donnerait quelque chose d'inédit. Parce que le "suprême-fasciste" peut lui aussi, au fur et à mesure, parcourir une liste d'algorithme et prendre systématiquement l'inverse de sa n-ème sortie. Et si jamais un algorithme prédisait les réponses du "suprême-fasciste" et que cet algorithme était dans la liste à une position m, alors à la m-ème sortie l'algorithme du "suprême-fasciste" différerait. Ça ne me semble pas violer la thèse de church-turing ?
Donc ce n’est pas un algorithme. On ne pourrait pas mettre en pratique ce pseudo-algorithme, parce qu’il faudrait pouvoir dire si un algorithme va s’arrêter ou non.
Salut , quelqu'un peut me faire comprendre pourquoi l'ensemble des suites que peut faire le suprême fachiste par les suites de chapeaux est dénombrable ? est-ce que l'ensemble des suites à valeurs dans {0,1} est dénombrable ?!
Non, l'ensemble des suites à valeurs dans {0,1} est indénombrable. Par contre, l'ensemble des suites à valeurs dans {0,1} qui peuvent être générées par des programmes, lui est dénombrable. Car l'ensemble des programmes est dénombrable (on peut lister tous les programmes de longueur 1, puis 2, etc.) donc son sous-ensemble est aussi dénombrable. Le paradoxe réside dans le fait que les 2 ensembles ont l'air d'être à peu près aussi grands, or non, le premier est fondamentalement plus grand que le deuxième.
Très intéressant comme d'hab. Juste une petite remarque, est-ce qu'on ne pourrais pas dire que la question n'existe pas car il y a une infinité de lapin et que donc on ne pourra jamais vérifier algorithmiquement si ils gagnent ou pas. PS : C'est quoi cette fortranphobie primaire ? #FortranLivesMatter
d'autant plus que le fortran est vraiment chouette (et tellement bien que depuis qu'on nous prédit sa mort il est encore plus vivant que jamais là où les modes passent)
J'ai adoré cette video. Mais elle me fait poser une question: si les lapins tombent par magie sur la liste des algorithmes qui terminent (on sors un peu du cadre mais tant pis), puis qu'on écris un algorithme qui utilise cette liste pour être différent de chacun de ses algorithmes (comme la diagonale de cantor). On construit alors un algorithme qui n'est pas dans la liste, ce qui nie sa dénombrabilité. Donc un sous-ensemble d'un ensemble dénombrable (pas au sens algorithmique) peut ne pas l'être?
ça ne nie pas sa dénombrabilité. ça nie juste que l'algo du SP termine. Du coup dans ce cas, le SP met une infinité de temps à choisir la couleur des chapeaux...
Pour faire leur algorithme, les lapins doivent savoir si chaque algorithme finit ou pas. Sinon, dès la phrase "while true then loop", leur algo ne donne jamais de couleur de chapeau. Donc les lapins ne peuvent pas construire leur méta-algorithme. D'ailleurs, si on pouvait faire ce genre de truc, on aurait d'autres contradiction, du genre diagonale de Cantor : soit l’algorithme qui donne la couleur opposée du premier chapeau de l'algo 1, puis la couleur opposée du second chapeau de l'algo 2, etc... Cet algorithme n'est pas dans la liste des algorithmes : contradiction.
Tu ne comptes pas les algorithmes qui te permettent de décider quelle couleur attribuer au n ieme lapin mais les suites de chapeaux blancs et noirs. Or toutes ( presque aucune même en un certain sens) ne sont calculables algorithmiquement.
et si c'est un algorithme qui récupère juste des données d'un comportement "réellement" aléatoire ? (comme utiliser des lampes de laves ou "bruit" de l'espace), les lapins ne pourront pas prédire les chapeaux suivants.
Pourquoi il ne les coifferai pas au hasard? Ou si il utilise un algorithme, il peut le changé après n tours et en utilisés un autres puis revenir à du hasard et ce, un infinité de fois
Je ne suis pas sûr de comprendre pourquoi les algorithmes sont dénombrables. On peut écrire une infinité non dénombrable d'algorithmes du genre: je prend un nombre x entre 0 et 1, et pour le lapin n si x^n a comme première décimale un chiffre paire il a un chapeau noire, sinon il a un chapeau blanc. Qu'est ce qui ne va pas dans mon raisonnement?
La plupart des réels entre 0 et 1 ne sont pas obtenables via un algorithme. Par définition un algorithme est une suite finie d'instructions, parfaitement décrite par une suite finie de 0 et de 1 (donc isomorphe à l'ensemble des entiers N )
Dès lors que SF peut établir un méta-algorithme anticipant toutes les réponses des lapins, il construit donc un nouvel algorithme non contenu dans l'ensemble initial. Dès lors, l'argument des lapins n'est il pas fallacieux car en réalité l'ensemble des algorithmes n'est pas vraiment dénombrable ?
Est ce qu'il est possible de faire marcher une stratégie ou les lapins ne prennent non seulement le nombres de lignes du programme mais aussi le nombres d'étapes qu'il faut pour l'exécution de ce programme ?
Non, car même si le programme doit terminer en un nombre fini d'étapes pour chaque lapin, le nombre d'étapes peut quand même croître à l'infini au fur et à mesure que les lapins augmentent. Par exemple, un programme qui fait N étapes où N est le numéro du lapin dont on décide le chapeau
@@SaiphxXx pourtant ça c'est bien une façon dénombrable de lister tous les programmes qui terminent: (cette stratégie ne marche que s'il existe qu'un nombre fini de programmes qui s'écrivent en une ligne sur python) On prend l'ensembles des programmes qui s'écrivent en une ligne sur python, on les faits marcher tous, mais seulement pour une étape de calcul, puis la on teste ceux qui se sont arrêtés après une étape Si aucun de ces programmes ne marchent on prends ceux qui ne se sont pas arrêtés et on les fait s’exécuter pour encore une étape, et on refait le processus On teste avec dans l'ordre les programmes de : 1 ligne arrêtés après 1 étape 1 ligne et 2 étapes 2 lignes et 1 étape , 2 lignes et 2 étapes 1 ligne et 3 étapes 2 lignes et 3 étapes 3 lignes et 1 étape 3 lignes et 2 étapes 3 lignes et 3 étapes 1 ligne et 4 étapes etc.
Je n'ai pas été convaincu par l'argument, pour le contourner ne suffit-il pas pour les lapins de simplement modifier leur manière de lister les algorithmes ? Par exemple, si au lieu de lister les algorithmes par la taille de leur code, les lapins listaient les algorithmes par le nombre d'instructions effectivement exécuté, alors les lapins ne resteraient plus bloqués à tester des algorithmes au temps d'exécution infini. De plus ce classement des algorithmes en nombre d'instructions effectivement réalisé peut se faire algorithmiquement, au début de la liste on mettrait par exemple les algorithmes qui s'exécutent en 1 instruction, on sait dès lors que l'algorithme a forcément un nombre d'instructions inférieur ou égal à 1 (si ça n'était pas le cas cela signifierait que certaines instructions ne sont pas exécutées auquel cas, elles n'ont pas à être prisent en compte). Si des algorithmes de 1 ligne exécute plus d'une instruction on peut alors le mettre de côté pour plus tard, lorsque l'on passera aux algorithmes qui nécessitent l'exécution de 2 instructions pour arriver à terme, il suffira d'abord de continuer l'exécution des algorithmes de 1 ligne qui n'avait pas fini de s'exécuter, en gardant de côté ceux qui n'ont toujours pas terminé après 2 instructions avant de faire de même avec les algorithmes de 2 lignes. De cette façon les lapins ne resteront jamais bloqués avec les algorithmes au temps d'exécution infini, car ceux-ci resteront tout simplement indéfiniment de côté. De mon point de vue les lapins ne vont pas réussir, mais pour une autre raison, dans leur stratégie, ils supposent que le suprême fasciste a un algorithme avec un nombre d'instructions bien déterminé, or, il suffit comme dans la vidéo que le suprême fachiste enrichissent son algorithme avec les réponses des lapins (avec par exemple un algorithme d'apprentissage) pour que la stratégie des lapins tombent à l'eau, de mon point de vue, c'est ici que réside l'erreur de raisonnement des lapins, l'algorithme du suprême fachiste s'enrichit continuellement de nouvelle instruction, donc même si les lapins testent toujours plus d'algorithme différent, ils ne trouveront jamais celui utilisé par le suprême fachiste tout simplement, car celui-ci se complexifie et s'enrichit au fur et à mesure des réponses des lapins (de la même façon que l'algorithme des lapins s'enrichit des choix de chapeau du suprême fachiste).
Le problème avec la stratégie "lister par nombre d'exécutions executées" est que le nombre d'instructions exécutées peut dépendre de l'argument en entrée (numéro du lapin), et qu'il peut augmenter à l'infini. Par exemple, voici un programme qui défait ta stratégie: def choisir_chapeau( N ) : i=0 while i < N+1: i = i + 1 return 0 Ce programme ne sera jamais dans ta liste
On dirait un argument de type diagonale de Cantor mais pour la calculabilité (l'algorithme du suprème fascite qui consiste à répondre le contraire de l'algorithme des lapins ne peut pas être dans la liste que suivent les lapins). Je crois qu'on oublie souvent les implications du tier-exclu et la force que représente la négation en logique tel qu'on nous l'apprend, après tout la démonstration par l'absurde est souvent le chemin qu'on aime prendre par défaut même quand ce n'est pas nécessaire
Je pense que de toute façon, le suprême fasciste n'aura pas le courage de réécrire tout les livres d'info en Fortran donc au pire on perd une infinité de lapin ...
Ouah merci pour ces découvertes des maths constructives ! D'ailleurs peut-on vérifier les théorèmes de la théorie des ensembles algorithmiquement, comme on le fait avec le langage coq pour les maths constructives ? Si ce n'est pas le cas, les maths de la théorie des ensembles sont assez subjectives...
Interessante video. En effet l'algorithme des lapins ne termine pas et donc ne marche pas. Cela dit, l'algorithme du supreme ne termine pas non plus, donc ca n'est pas une preuve que les lapins sont sauvés (bien qu'a mon avis, on ne peut pas les sauver, mais je n'ai pas de preuve). Il me semble que si tu enleves la restriction a la logique constructiviste, les lapins sont sauvés si et seulement si tu as l'axiome du choix (pas 100% sûr à propos du "seulement si"). Dans tous les cas, ca semble difficile que dans notre univers, les lapins puissent etre sauvés, parce que ca voudrait dire qu'ils voient l'avenir. Donc avoir une theorie mathematique (que l'on suppose valide pour notre univers) qui permette de sauver les lapins me semble difficile a concilier avec une vision classique causale du monde. Meme dans un univers purement deterministe comme presenté dans ce probleme, le determinisme de l'univers depend de variables que l'on ne connait pas. En tous cas, ca serait terriblement contre-intuitif et les implications seraient tres interessantes si en effet, les lapins pouvaient gagner (dans un modele mathematique qui corresponde a notre univers).
Ah mais en fait, en y réfléchissant, est-ce que le supreme connait l'algorithme des lapins? Dans la video, il semble que oui, et dans ce cas, évidemment que l'algorithme du supreme va terminer et qu'il va gagner. Quand je dis que je n'ai pas de preuve que le supreme gagne, c'est dans le cas où le supreme ne connais pas l'algorithme des lapins.
Ni les lapins ni le suprême fasciste ne peuvent avoir une stratégie qui fonctionne toujours, dans un univers régit par la loi de Church-Turing. En effet, par l'absurde, si l'un des deux a une stratégie gagnante, cette stratégie gagnante est un algorithme, et cette stratégie gagnante doit fonctionner peu importe l'algorithme qu'utilise l'adversaire. Or l'adversaire peut tout à fait utiliser l'algorithme contraire (pour le suprème fasciste) ou le même algorithme (pour les lapins), et gagner, ce qui est absurde. Aucun des deux groupes n'a une stratégie gagnante.
@@VeganCookies Bah, ca depend de qui connait quoi dans la definition du probleme. - Je pense qu'il est clair que les lapins ne connaissent pas l'algorithme du supreme. Sinon, il n'y a aucune raison d'énumerer les algorithmes, les lapins gagnent toujours. - Est-ce que le supreme connait l'algorithme des lapins ou pas? A 7:20 Lê dit que oui, donc admettons que oui. Dans l'exemple que tu donnes, tu dis que la strategie doit etre gagnante peu importe l'algorithme qu'utilise l'adversaire, mais ca n'est deja pas du tout le cas si il y a une asymétrie dans l'information, telle qu'elle est présentée ici. Ici tu supposes que les lapins connaissent la strategie du supreme, et je suis a peu pres sur que ca n'est pas le cas.. Il me semble que tu fais plutôt reference à des équilibres de Nash, mais ca s'applique quand les 2 joueurs connaissent la strategie de l'adversaire.
@@myrhev42 Je ne suppose pas que les lapins connaissent la stratégie du suprême, ni que le suprême connaît la stratégie des lapins. Mon commentaire s’applique dans ce cas. Si le suprême connaît la stratégie des lapins, alors effectivement il gagne de toute façon, puisque la stratégie des lapins doit être un algorithme qui termine, il peut donc prendre à chaque fois la valeur inverse. Je n’avais pas pensé au problème de cette façon.
Pour n'importe quelle combinaison de chapeau, l'algorithme du super-faschiste peut forcément se rapporter à : - choisir un nombre réel - le transposer en base 2 - assigner à chaque lapin un chiffre (le premier lapin à le premier chiffre, le 2ème lapin à le 2ème chiffre, etc.) - si le chiffre du lapin est 0 alors il a un chapeau noir sinon il a un chapeau blanc Or il y a une infinité de nombre réel Donc les lapins se tromperont forcément une infinité de fois (Je sais pas si mon raisonnement est bon mais c'est la première chose qui m'est venu à l'esprit)
Hum il pourra uniquement prendre des nombres réels calculables algorithmiquement. Cela fera une infinité dénombrable (au sens classique) de nombres réels que les lapins pourraient énumérer s'ils se bornaient aux algorithmes valides et donc à un moment ou à un autre tomber sur celui-ci ce qui comme le montre la vidéo n'est pas possible
Mais y'as pas moyen de simplement attribuer les chapeaux au hasard? Genre disons en mesurant l'état quantique d'une particule avant d'attribuer un chapeau. Tu arrives à un résultat où les lapins peuvent avoir raison très fréquement parce qu'ils arrivent à deviner la distribution des probabilité des états quantiques de cette particule mais ne peuvent pas garantir une bonne prédiction et sont donc garantis de se tromper de temps en temps.
@@zedzed3533 Bah l'algorithme est déterministe. c'est une simple mesure avec "si A => alors B" "si non-A => alors C". C'est le monde qu'on mesure qui n'est pas déterministe =p Après tu peux ajouter ça comme exception à ton expérience de pensée mais ça commence à faire pas mal de règle arbitraire, déjà qu'on doit imaginer une infinité de lapin y'as un moment ton expérience de pensée veut plus rien dire. Si on éliminie les solutions au problème en ajoutant une règle arbitraire qui les interdit c'est assez facile de créer des tas de problèmes impossible à résoudre.
@@Laezar1 Tu pars du principe que les seuls données que tu connais ce sont les lapins et leurs couleurs de chapeaux après si tu changes les règles tu peux faire beaucoup de choses
@@zedzed3533 Bah il s'agit juste de savoir si il y à un algorithme qui même une fois connu peut générer une infinité d'erreur, y'a à priori aucune limitation sur ce qu'on peut inclure dans cet algorithme. Ou alors fallait rajouter les règles dans l'énoncé.
Avant de voir la réponse : J'avais déjà réfléchis à un paradoxe semblable impliquant les conséquences du fait que le comportement humain serait prévisible (dans le sens ou il serait possible de connaître avec une précision satisfaisante le comportement d'un humain dans un court laps de temps) Dans ce cas il serait possible de faire une machine qui prévoit le comportement d'une personne avent que celui-ci ai lieu, mais comme condition il doit le montrer à la personne Seulement que cette personne est rebelle et veut faire mentir la machine, du coup quel que soit la prédiction que fait cette machine, il veut la faire résulter fausse , et la machine connait ce paramètre sur les facteurs influençant le comportement de cette personne Du coup comment va se comporter le système machine-personne?
Est ce que cette stratégie marche : (cette stratégie ne marche que s'il existe qu'un nombre fini de programmes qui s'écrivent en une ligne sur python) On prend l'ensembles des programmes qui s'écrivent en une ligne sur python, on les faits marcher tous, mais seulement pour une étape, puis la on teste ceux qui se sont arrêtés après une étape Si aucun de ces programmes ne marchent on prends ceux qui ne se sont pas arrêtés et on les fait s’exécuter pour encore une étape, et on refait le processus On teste avec dans l'ordre les programmes de : 1 ligne arrêtés après 1 étape 1 ligne et 2 étapes 2 lignes et 1 étape , 2 lignes et 2 étapes 1 ligne et 3 étapes 2 lignes et 3 étapes 3 lignes et 1 étape 3 lignes et 2 étapes 3 lignes et 3 étapes 1 ligne et 4 étapes etc.
On peut faire ça, et c’est effectivement une manière de lister tous les programmes qui s’arrêtent. Par contre, cela ne permet pas aux lapins de gagner, puisque si le temps que prend la stratégie du suprême fasciste peut croître très rapidement, obligeant les lapins a changé constamment de programmes pour chaque nouvelle étape du jeu.
@@VeganCookies j'étais justement en train de penser à ça et en fait c'est pas nécessairement un problème car les lapins peuvent déjà voir si le programme aurait été bon rétrospectivement entre deux choix, et vu que le programme du suprême fasciste est d'office un programme qui comporte un nombre fini de lignes et un nombre fini d'étapes les lapins vont d'office tomber dessus
*pause à **8:00* Je pense que l'erreur des lapins est de supposer que connaître l'algorithme suffit. Sauf que pour connaître le résultat d'un algo il faut aussi connaître les paramètres de cet algo, et ça ce n'est pas nécessairement énumérable. *fin du visionnage* Ok, effectivement, et dit comme ça c'est tellement gros que je me sens un peu nul de ne pas y avoir pensé^^
J'avais aussi parié sur le suprême fasciste, mais pour une autre raison : Si on peut supposer que le suprême fasciste peut connaître le plan des lapins, on peut aussi supposer qu'il utilise un algorithme qui utilise comme donnée le choix de couleur que font les lapins, pour déterminer la couleur du prochain chapeau. On peut alors imaginer que l'algorithme du suprême fasciste s'affine en "devinant" quels algorithmes ont été essayés par les lapins. Il a alors en permanence un coup d'avance, car l'algorithme qu'il utilise est forcément plus loin dans la liste des lapins, car il contient, en quelque sorte, les algorithmes déjà essayés.
Bon j'ai mis pause à 8:06. Mais de manière générale c'est l'hypothèse de départ qui est discutable : peut on changer d'algo en cours de route ? Par exemple, le SF , s'il voit que les lapins ont raison plus de x fois, change d'algorithme aléatoirement : alors il y aura forcément une infinité d'erreurs. SI l'algorithme du SF est variable, les lapins finiront en civet et nos programmes en fortran. Pourtant ce changement d'algo... Peut être un algo. Dans ton exemple tu confonds un algorithme avec une séquence de chapeaux : le choix du SF ne dépend pas des réponses des lapins. Par contre le choix des lapins est influencé par les choix précédents du SF. Il n'y a pas une infinité de séquences possibles mais à chaque moment, si le SF change, il y a une infinité de séquences ultérieures possibles. C'est donc la stratégie des lapins qui est basée sur un choix fallacieux, car basé sur le fait que l'algo du SF est en quelques sortes "stable". Et il est facile d'en trouver qui ne le soient pas. Allez je vais voir la suite, bisous Edit : Je pense que j'ai tapé pas loin, si je comprends bien les lapinous partaient du principe qu'ils pouvaient lister ces algorithmes, en fait non car il y a justement des algorithmes qui ne s'arrêtent pas (ceux que j'ai proposés et celui que tu proposes aussi en contre exemple sont effectivement des algos qui ne s'arrêtent pas) . Pire qu'absents d'une éventuelle liste, ils ne peuvent juste pas être listés. Merci en tout cas pour ce noeud cérébral qui va hanter ma semaine ;)
S'il change d'algorithme après un certain nombre d'échecs, les lapins n'auront qu'à trouver dans quel ordre "aléatoire" les algorithmes sont choisis (par un algorithme) et après combien d'erreurs. Le problème, c'est s'il est seulement possible en un nombre fini d'essais de trouver le bon algorithme. Personnellement j'avais pensé que c'était impossible si l'algorithme utilise une seed, alors pour un seul algorithme, il faut tester toutes les seeds possibles, mais étant donné qu'on ne connaît pas la taille de la seed, on ne peut jamais terminer.
@@al8-.W Je dirais oui, en fait dans ce cas on reproduit schématiquement ce qu'il se passe dans le cadre favorable aux lapins mais avec hélas un nombre infini d'erreurs car on remet une pièce à chaque fois que les lapins ont un certain nombre de réussites. Reste sinon au SF à simplement changer d'algo à chaque coup et là la stratégie des lapins, je pense quelle qu'elle soit, ne peut que voler en éclat et nous serons tous condamnés au fortran. Je crois qu'en fait il est facile de trouver des scénarios pour lesquels le SF est imbattable. Après je pars du principe qu'un "nombre fini d'erreurs" se traduit par le fait qu'à compter d'un certain point , les lapins auront toujours raison. Ce point peut ne jamais arriver selon la stratégie d'algos du SF
Les algorithmes finis et infinis sont mélangés. En choisissant comme algorithme les plus courts d'abord mais aussi ceux tournant le moins d'abord, les lapins ne peuvent-t-ils pas parer à la faille? 1 ligne et 1 tour, 1 ligne et 2 tours, 2 lignes et 1 tour, 2 lignes et 2 tours...
Fichtrement intéressant ! ^^ Sans ignorer cette vidéo, je change de sujet: j'ai une question qui me semble assez importante, car je suis à la croisée des chemins, et j'hésite. Quels études à tu fais pour arriver à ce stade de connaissances ? Fac ? Prépa ? Ou juste des livres/vidéos 😅 ? (Et si quelqu'un aurait déjà posé cette question, sur quelle vidéo puis-je trouver réponse ? Merci beaucoup !!!) Au passage je voudrais te dire que j'adore toutes te vidéos, et que c'est génial d'écouter et de comprendre un passionné ! Bonne journée
En fait, je ne vois rien qui permet d'affirmer avec certitude qu'il existe un nombre fini d'algorithmes décrivant la situation. Après tout n'est-il pas possible de faire en sorte que l'algorithme le plus simple pour décrire la couleur du chapeau soit la liste des couleurs des chapeaux de tous les lapins ? Ces derniers étant une infinité...
Pour moi les lapins sont voués à l'échec car le suprême peut aussi utiliser le hasard plutôt qu'un algorithme. Dans ce cas, ou bien les lapins devront répondre au hasard mais ainsi feront des erreurs à l'infini, ou bien essayer de déterminer un algorithme (le leur, ou qui un essaye d'en identifier un utilisé par le suprême) mais dans ce cas le suprême prend forcément l'avantage, comme dit dans la vidéo. Mais la solution pour les lapins réside peut-être dans la notion d'infini. Les lapins obligent le suprême à aller jusqu'au bout de l'infini pour qu'il soit sûr qu'à aucun moment les lapins ne "prennent le dessus à l'infini". On parle de compter à l'infini là ! Si les lapins font un gogoplex de succès, le suprême va toujours essayer de chercher sa victoire, et le peut ; si les lapins font un gogoplex de défaites, ils pourront toujours demander à continuer leur chance, et statistiquement ça se pourrait, à l'infini... Ainsi, jamais jamais le suprême ne pourra lui-même venir à bout du défi qu'il a lancé, et les lapins vivront pour toujours sans inquiétude ! Seul Chuck Norris a compté jusqu'à l'infini. Deux fois, dont une en partant de la fin.
Je ne comprend pas bien la non-denombrabilité des algorithmes qui terminent : Étant donné une énumération de tous les algorithmes, il suffit d'exécuter: L'instruction #1 de l'algo #1 L'instruction #2 de l'algo #1 et l'instruction #1 de l'algo #2 ... Les instructions #(n-k) de l'algo #k, pour k entre 0 et n : si l'algo #k termine on lui donne une étiquette, et s'il est déjà terminé on le saute. En procédant ainsi, on va pouvoir "exécuter en parallèle" tous les algorithmes, et ainsi finir par étiqueter tous ceux qui terminent (et donc obtenir un dénombrement sans axiome du choix) Il me sembleraient donc que seuls les algos qui ne terminent pas sont indénombrables.
Je pensais qu'il était impossible qu'une infinité de lapins se rappellent parfaitement des algorithmes et les exécutent tous dans un temps raisonnable, et ce sans jamais faire d'erreur...
peut-être que la meilleure stratégie pour les lapin est de décider de garder secrète leur stratégie (qu elle qu elle soit). Du coup le seul moyens pour savoir qui gagne sera de mener l expérience jusqu'à l infini alors que chacune des étapes dure un temps non nul... et le monde est sauvé 🥳🥳🥳
je pensais la réponse allait etre quelque chose du type "diagonale devastatrice de Cantor" où les lapins dénombrent un infini mais le diable peut toujours trouver quelque chose qui n'est pas contenu dans cet infini
La meilleure solution pour tuer tuer tous les lapins serait le tirage au sort pour choisir la couleur des chapeaux 🤠. À moins d'avoir l'obligation d'utiliser un algorithme.
Le truc du sous ensemble non dénombrable dans un ensemble dénombrable m‘a perturbé jusqu‘a ce que je comprenne que cela veut dire qu’en réalité ce sous-ensemble est bien dénombrable mais qu’on ne peut pas le construire
7:50 Mais... L'algorithme du suprême fachiste pourrait être numéro infini quelque chose, non ? Genre yaurait une infinité de mauvais algorithme avant, donc une infinité de mauvaises réponses...
Tout dépend ce que tu appelles infini et "plus grand que". En tout cas en mathématiques classiques, IN^IN l'ensemble des applications de IN dans IN a la puissance du continu et est donc de cardinalité supérieure à la cardinalité de IN.
@@edwinvital1206 Plus petit que quoi ? Je ne vois pas où tu veux en venir. Ensuite ben, non, 2^Aleph_n n'est pas nécessairement égal à Aleph_n+1, ça impliquerait en particulier que 2^Aleph_0 = Aleph_1 ce qui est exactement l'hypothèse du continu (est-ce que le cardinal de P(IN) est le plus petit cardinal supérieur au cardinal de IN ?). Or on sait que l'hypothèse du continu est indécidable dans ZF(C).
J'aimerais argumenter que, dans notre expérience, le problème de l'arrêt n'est pas valable, car on suppose les lapins et le SF infiniment intelligents, a minima pour que les lapins puissent trouver en moins de 10 secondes une solution qui peut nous prendre des jours à déterminer. Or, le problème de l'arrêt demande que une opération, quelque soit sa complexité, ne puisse être résolue qu'en un temps non nul, car il faut qu'il existe un algorithme qui ne boucle pas, mais que sa résolution se fasse sur une échelle de temps qui, à l'échelle de l'observateur, soit assimilable à l'infini. Sauf que, si les lapins prennent un temps non nul à faire des opérations: soit le SF leur laisse un temps (absolument) infini pour résoudre son problème, auquel cas les lapins ont tout leur temps pour réaliser les algorithmes, et peuvent se permettre d'attendre une infinité de secondes pour essayer de résoudre l'algorithme avant de passer au suivant, (On peut dire que le lapin se pose ꞷ0 secondes avant de déduire que l'algo boucle, pendant que les autres vont faire une sieste chez Hilbert qui a posé son hôtel pas loin), dans ce cas le problème de l'arrêt n'est plus un problème, Soit le SF laisse un temps T à chaque lapin pour faire un choix, mais le problème est trivialisé car il suffit au SF de choisir un algorithme qui, quelque soit sa manière de le définir, demande un nombre d'opérations supérieur à T/𝜏, avec 𝜏 le temps nécessaire à un lapin pour réaliser une opération, et attendre juste le moment inévitable ou les lapins n'auront pas assez de temps pour résoudre l'algorithme. Dernier cas, les lapins infiniment intelligents font des opérations en un temps nul, ainsi ils peuvent déterminer instantanément si un algorithme boucle, et le problème de l'arrêt ne se pose plus.
Mon hypothèse c'est qu'on a oublié de préciser que le suprême fasciste doit utiliser un algorithme qui termine et j'ai franchement l'impression que celui là ne termine pas
S'il était possible de lister les algorithmes qui terminent, ne serait-il pas possible de battre les lapins avec l'algorithme suivant : - Le fasciste, disposant également de la liste, utilise arbitrairement un algorithme de la liste pour commencer (disons la liste numéro i) - si les lapins ont un grand nombre de réussite successives, le fasciste utilise un algorithme pseudo-aléatoire pour récupérer un nouvel indice d'algorithme à utiliser, pour que les lapins recommencent à se tromper - Les lapins ne peuvent ainsi jamais trouver le bon algorithme, car l'algorithme change quand ils le trouvent J'imagine que le point faible de cet argument pourrait résider dans la supposition qui existe un algorithme pseudo aléatoire pour ressortir un nombre entre 1 et l'infini. Je ne sais pas si un tel algorithme est concevable (entre 1 et n, c'est possible, mais là j'en ai aucune idée)
Un algorithme pseudo-aléatoire est toujours un algorithme, donc il doit être dans la liste, et donc si les lapins ont accès à la liste, ils finiront pas le trouver et à suivre exactement les changements d’algorithme du fasciste.
Rien compris... 🥺 C'est la première fois que ça me fait ça... Si le suprême machin choisir des chapeaux au hasard,.les lapins ont perdus et on arrête là non ?
Je pense qu'il ne peut pas faire ça car ses choix doivent pouvoir être calculés par la thèse de Church-Turing (donc par un algorithme). Le hasard ne peut pas être "calculé".
J'avais pensé à un autre argument contre les lapins, mais je ne saurais pas dire si il est valide : Le jeu étant fait en itérations (les lapins se présentent les uns après les autres, et doivent déterminer la couleur de leur chapeau avant que le suivant arrive), le suprême fasciste pourrait se rendre compte que les lapins ont découvert son algorithme et en changer subitement non? Par exemple après un grand nombre de réussite des lapins, ce qui suggèrerait qu'ils sont sur la bonne voie, il peut choisir un tout nouvel algorithme, et ainsi de suite à chaque fois que les lapins ont les longues séries de réussite ( dix, cinquante, un milliard... peu importe).
Sauf qu'il existera un algorithme qui le prédit malgré tout: Si le SF suit l'algorithme A pour les 10 000 premiers chapeaux, mais qu'il décide ensuite de changer pour prendre l’algorithme B, il arrivera un moment ou les lapins atteindront un algorithme que l'on nommera C, qui est {Pour le N-ieme chapeau, si N
Il y a deux éléments qui me perturbent dans cette histoire. La première est de parler d'algorithmes qui s'arrêtent sensés construire des listes infinies. La seconde est le problème de la vitesse de calcul. Soit celle ci est finie auquel cas il n'y a pas besoin de faire la liste des algorithmes s’arrêtant toujours. Il suffit de prendre la liste, dénombrable, de tout les algorithmes, et de ne considérer que ceux qui ont rendu un résultats après n opération (qui peut dépendre du numéro du lapin). Soit elle est infinie et les algorithme ne s’arrêtant jamais s'identifient d'eux même dans la la liste (ce sont les seul à ne pas s’arrêter immédiatement). Au final, j'ai l'impression que les lapins ne perdent que si le suprême fasciste est le seul à posséder une vitesse de calcul infinie. J'aurais tendance à quand même faire gagner le fasciste, car si il a accès à la même liste que les lapins, il peut tout à fait changer d'algorithme à chaque lapin pour prendre un algorithme plus loin dans la liste (un revenir sur un algorithme qui aurait donné un résultat erroné sur un lapin déjà venu est aussi un algorithme, par contre je sais pas le placer pour être sûr de rester en avance sur les futurs ragouts).
Personne n'a jamais besoin d'attendre le tirage d'une suite infinie dans l'histoire. Le suprême fasciste peut très bien tirer le n-ième chapeau seulement au moment où le n-ième lapin arrive et les lapins n'ont quant à eux pas la prétention de tirer une suite infinie, mais de tirer une couleur à chaque fois.
Peu t on faire un nombre aléatoire avec une machine de Turing... (Algorithme du SF)... Sinon, la sequence des lapins antérieur peut permettre de trouver l algorithm pseudo-aléatoire du SF.
@Science4All Mais si les lapins possèdent déjà la réponse, je veux dire, s'ils ont déjà un tableau infini mais déjà construit liants chaque algorithmes avec le fait qu'il finissent ou non ? ils n'ont alors pas besoin d'utiliser un algorithmes pour déterminer quels algorithmes finissent ou non, ils suivent juste leur tableau déjà construit et peuvent ainsi savoir la bonne réponse. Et dans ce cas qui se trompe ? Toujours les lapins ? (remarque peut-être qu'en disant ça je te demande juste : "Et si la thèse de Turing était fausse ?", j'ai du mal a savoir ^^')
Le problème, c'est toujours le même : l'infini. Notre définition de l'infini, c'est que c'est l'ensemble de toutes les possibilités. Comme dans les décimales de Pi: parce qu'elles sont infinies, on peut y trouver toutes les suites de nombres possibles. C'est un problème axiomatique. Les scientifiques tournent en rond dès qu'il s'agit de l'infini. Par exemple, la diagonale de Cantor est fausse : la liste de Cantor étant infinie, elle contient tous les nombres possibles .. mais Cantor crée un nombre qui ne peut être contenu dans sa liste .. C'est un paradoxe !!! Dès qu'on étudie l'infini, on aboutit à plein de paradoxes !! D'après le théorème d'incomplétude de Godel, notre système axiomatique est faux: notre définition de l'infini est fausse. Mais les gens comme Lê préfère continuer à tourner en rond, comme avec ce genre de vidéo .. ♉♉♉
+1000 Un autre paradoxe qu'on obtient en faisant des calculs avec des infinis c'est la fameuse "somme de tous les entiers positifs qui serait "égale" à -1/12, alors qu'une telle somme devrait "converger vers + l'infini". C'est pour ça que j'ai toujours considéré que chercher à utiliser l'infini dans un calcul mathématique c'est aussi insensé que chercher à utiliser Dieu comme paramètre dans une équation de physique : ça part très vite en cacahuète.
Je pense que vous regardez trop de vidéos vulgarisatrices de maths ... L'infini est très bien cadré en mathématiques, ce que dit Lê peut être décrit très formellement sans aucun paradoxe et ne tourmente aucun mathématicien... d'ailleurs il n'y a pas de paradoxe puisque le raisonnement des lapins est faux ... quand à la somme 1+2+3+... qui vaut -1/2 , je ne sais pas quelle vidéo à sensations vous avez vu mais c'est un abus de notation énorme valide uniquement dans un contexte particulier où l'addition n'est plus du tout ce que vous croyez (c'est même mensonger d'utiliser le signe "+" ). Dans la formule 1+2+3+... les nombres 1,2,3 ne sont pas des nombres et le symbole "+" n'est pas l'addition, et -1/12 n'est pas non plus le nombre -1/12 ... Pour écrire 1+2+3+... = -1/12 formellement on doit d'abord faire 10 pages de définitions et redéfinir absolument tous les symboles usuels, en particulier on doit définir la fonction zéta de Riemann et autres bizarreries juste pour pouvoir décrire ce fameux "+", ce qui requiert au moins des maths BAC+2, donc ce "+" n'a VRAIMENT rien à voir avec l'addition... Si quelqu'un vous a prétendu que 1+2+3+... = -1/12 sans vous préciser que + n'est pas l'addition dans cette formule c'est soit qu'il n'a rien compris non plus soit qu'il veut vous tromper purement et simplement. C'est comme si je disais qu'à partir de maintenant je note la multiplication avec le symbole + et que je vous dis "3 + 3 = 9 !!!! incroyable" mais sans vous préciser ce que signifie mon "+". Dans les notations usuelles où 1,2,3 sont des nombres entiers la série 1+2+3+... diverge vers +l'infini et personne ne conteste ce résultat.
@@SaiphxXx Vous voyez, vous le constatez par vous même : vous écrivez vous même que tout dépend de nos définitions. Le signe + ou ×: vous utilisez cet exemple. ( 1+2+3 ... =-1/12; c'est la somme de Ramanujan, Lê a fait une vidéo sur le sujet) Vous prenez un autre exemple pour dire la même chose que moi: tout dépend de la définition que l'on donne à quelque chose. C'est un problème axiomatique. Le problème, c'est la définition de l'infini en mathématiques .. Ce n'est pas sur les calculs que les scientifiques bloquent ; ils bloquent sur la notion elle même de l'infini. C'est quoi l'infini ? Un ensemble de toutes les possibilités ? Donc c'est normal que infini=-1/12.. Ou alors, les décimales de Pi sont infinies, donc infini=Pi ? La fraction 1/3 est un nombre rationnel .. et pourtant les décimales sont infinies 0,3333 ... donc infini=1/3 ? Alors oui, de nos jours, on est capable de démontrer n'importe quoi, comme 1+2+3 ...=-1/12 .. On est capable de le démontrer en mathématiques !!!! Ça prouve bien que le problème est axiomatique .. Le problème, c'est la définition de l'infini .. ♉♉♉
@@pierrestempin100 Somme 1+2+3...=-1/12 Somme 1+1/4+1/16 ..=-1 0,99999....=1 Les décimales de Pi sont infinies .. 1/3= 0,33333 ... Etc .. etc ... Donc c'est quoi l'infini ? Infini=-1/12=-1=1/3=Pi ...???? Pierre, si je vous dis : un ensemble E, des nombres entiers entre 1 et 9. 1, c'est correct 2, c'est correct 7, c'est correct Notre définition de l'infini, c'est que c'est un ensemble !!! Un ensemble à l'infini !!! Donc, comme pour l'ensemble E, je peux dire pour l'infini: -1/12, c'est correct -1, c'est correct Pi, c'est correct 1/3, c'est correct Vous comprenez Pierre ? Le problème, c'est qu'à cause de notre définition de l'infini, on peut donner à l'infini n'importe quelle valeur !!! Et c'est exactement ce qu'il se passe .. on peut démontrer n'importe quoi, ça sera toujours correct !!! Comme la somme de Ramanujan .. ♉♉♉
@@SaiphxXx Pour les vidéos et vulgarisations liées la somme des entiers positifs "égale" à -1/12 : MicMaths a fait une vidéo dessus : th-cam.com/video/vMnkmBCvGQc/w-d-xo.html Science étonnante a fait un billet de blog dessus : sciencetonnante.wordpress.com/2013/05/27/1234567-112/ Numberphile a fait une vidéo dessus (en anglais) : th-cam.com/video/w-I6XTVZXww/w-d-xo.html Et ils vont tous dans le sens de "ce résultat incroyable mais vrai" et sans redéfinir le moindre terme utilisé dans l'équation. Lê aussi a fait une vidéo dessus : th-cam.com/video/xqTWRtNDO3U/w-d-xo.html et il est le seul à mettre en avant la contradiction 1=0 que montre un des commentateurs du billet de blog de Science étonnante en suivant un tel raisonnement. A titre personnel, ce qui me dérange, c'est pas tant l'utilisation (non-redéfinie) de l'addition que celui de l'égalité. Autant je suis prêt à accepter la proposition "la somme de 1 à n TEND VERS + l'infni" quand n TEND VERS + l'infini". J'accepte l'aspect cadrant de l'infini, mais pas son utilisation telle quelle comme nombre ou cardinal au sein d'un calcul.
j'en suis à 8:01 et ça ressemble fortement à du Cantor en binaire, en remplaçant 0 et 1 par noir et blanc. Les lapins ne font que lister les possible listes de et 0 de 1 possible (en passant par les algos qui les créé) sauf qu'il y en a une infinité (dénombrable) le suprême fasciste essaie d'en rajouter une n'étant pas dans la liste. Donc plusieurs possibilité : 1) la liste des lapins n'est pas complète et donc il existe une infinité non dénombrable d'algorithme possible (ce qui est contredit par la thèse de Church Turing) 2) Un algo qui prédit la technique des lapins est impossible. 3) La liste des algorithmes possible n'est pas faisable (mais comme leur infinité est dénombrable...) bon après j'écris ça à 6h du mat en 5 min donc il y a forcément des erreurs de raisonnement peu être même grossières.
Mais du coup, si le n-ième lapin doit attendre indéfiniment que les algorithmes soient calculés avant de faire sa prédiction, alors il ne fera jamais sa prédiction. Cela implique donc qu'il n'y aura jamais de cas dans lequel il y aura plus de n-1 prédictions effectuées, et donc plus de n-1 erreurs commises. Le nombre d'erreur des lapins sera donc bel et bien fini avec leur stratégie.
Je parierais sur les lapins : Est-ce que tout ne se ramène pas à une question de "puissance de calcul": les Lapins étant beaucoup plus nombreux (une infinité même ?) Devraient pouvoir créer un modèle du fachiste (par exemple un réseau de neurones) dont la complexité de Solomonof est comparable au cerveau du fachiste. Le fasciste lui, du fait de ses ressources limitées, est incapable de modèliser l'ensemble des lapins avec un niveau de complexité comparable. Les lapins devraient donc être capables de prédire de manière exacte le comportement du fasciste, ce qui n'est pas réciproque.
Je n'ai peut-être pas bien compris les règles de départ, mais pour moi, il me semblait évident que le suprême fasciste ne pouvait pas perdre : il lui suffit de lancer une pièce à chaque nouveau lapin qui arrive. Il donne un chapeau banc si c'est pile, un chapeau noir si c'est face. Puisque la distribution est aléatoire, les lapins auront une chance sur deux de se tromper, ils se tromperont donc en moyenne une fois sur deux. Puisqu'il y a une infinité de lapin, il se tromperont une infinité de fois. Où réside mon erreur de raisonnement ?
3:24 si je comprend bien la thèse de Chruch-Turing, on peut en conclure que, parmi tous les algorithmes existants, il y en aura un qui produira une simulation parfaite de l'univers, et dont le résultat sera si la pièce atterrit sur pile ou face. Donc une fois que les lapins auront atteint cet algorithme, ils en déduiront le résultat du jet. Et si le suprême fasciste décide de changer de méthode une fois que les lapins ont trouvé cet algorithme, il existe un algorithme qui est comme le premier, mais qui en plus prédit parfaitement le comportement mental du suprême fasciste, cad que l'algorithme prédit les changements d'algorithme du suprême fasciste.
Comment le faschiste fait-il pour choisir un algorithme ? Il est soumis au meme probleme d'arret que les lapins. Le faschiste doit choisir un algorithme parmi ceux dont il peut calculer qu'ils terminent. Les lapins peuvent donc faire la liste de ces algorithmes la.
Pour presiser mon commentaire peut etre un peu confus : Le sous ensemble des algo qui termine n'est pas denombrable, mais le sous ensemble des algo dont on peut calculer qu'il termine lui est denombrable (enfin c'est mon intuition). Hors c'est parmi ce dernier que le fashiste prend son algorithme.
@@MrDarkPage De une, c'est pas si évident que le suprême fasciste prenne forcément un algorithme qui termine prouvablement. De deux, ça me paraît trèèès peu probable que l'ensemble des algorithmes qui se terminent prouvablement soit algorithmiquement dénombrable.
Si j'étais un lapin je ne m'inquieterai pas On ne peut pas faire une infinité d'erreurs en un temps fini Et si j'etais un lapin je ne voudrai pas vivre eternellement
Dans le cas où le suprême fasciste applique l'algorithme qui consiste à appliquer l'algorithme global des lapins, puis à inverserser la prédiction pour chaque lapin, que se passerait-il dans le cas suivant : cet algorithme du suprême fasciste est le n° 60 000 000 dans la liste des algorithmes des lapins, et tous les algorithmes précédents de cette liste ont terminé. Les lapins ont donc fait 59 999 999 erreurs jusque là. Arrivés au lapin n° 60 000 000, ils font tourner l'algorithme n° 60 000 000, qui est donc l'algorithme du suprême fasciste. Que se passe-t-il alors ? Les lapins peuvent trouver la bonne réponse ? Le suprême fasciste boucle à l'infini ? Les lapins aussi ?
Argument pro-lapin : Le temps ne peut être mesuré sur des intervals inférieurs au temps de Plank. Il est donc raisonnable de penser que l'échange avec chaque lapin ne peut être plus court que celui-ci. De plus, l'univers à une durée de vie finie (voir th-cam.com/video/11XQUHOU_aw/w-d-xo.html de Balade Mentale). Cela borne le nombre de réponses possibles faites par les lapins à une quantité finie, rendant impossible un nombre d'erreurs infini.
Source de ce que tu avances sur le temps de Planck ? Le temps de Planck c'est juste le plus petit temps faisant sens vis à vis du déplacement d'une particule, mais rien n'indique que toutes les particules de l'univers soient synchrones. Pour parler grossièrement, tu pourrais très bien avoir un atome qui "s'update" tous les t = 0 mod tp et un autre atome qui "s'update" tous les t = tp / 2 mod tp où tp est le temps de Planck, auquel cas ton système évolue avec un pas de tp/2.
@@neloka4313 Je ne pensait pas au temps nécessaire pour choisir la couleur du chapeau mais à celui nécessaire pour échanger l'information entre le suprême fâchiste et les lapins. Puisque ce sont des entités physiquement discernables, elles sont séparée par une certaine distance au moins égale à la distance de plank. Ce fesant, tout transfert d'information met alors un temps de plank pour aller de l'un à l'autre.
en fait voila ce que doivent faire les lapins : le premier se place le 2ieme lapin voit un chapeau noir il se place a droite du lapin, si le chapeau est blanc il se place a gauche le 3ieme et les suivants : ils regardent la couleur des chapeaux et se positionnent entre les 2 lapins qui ont des chapeaux différents ou bien a droite du dernier blanc ou a gauche du dernier noir. ainsi le lapin précédent est capable de connaitre sa couleur car la position du lapin suivant lui donne l'information, seulement le dernier ne connaitra pas sa couleur... le supreme faciste ne peut donc pas gagner. peut importe l'algorithme choisis pour distribuer les chapeaux..
Morte de rire, la "Fortranpocalypse" :D Cela dit le Fortran est encore utilisé aujourd'hui dans le domaine du calcul parallèle hautes performances (et pas seulement dans le cadre de la maintenance de vieux programmes). J'ai bossé dans une équipe qui l'utilisais, et encore l'autre jour j'ai un ami qui m'a exhibé fièrement son exemplaire de "Modern Fortran" :D Je me dis que ça ne doit pas être un si mauvais langage du coup.
Si les lapins se trompent une fois sur deux, ils auront une infinité de bonnes réponses, ce n'est pas suffisant pour empêcher d'avoir une infinité de mauvaises réponses. Il leur faut un moyen de ne plus se tromper après un certain nombre d'essais.
Je vais quand même défendre le Fortran: dans ses dernières versions (90 et +) c'est un langage qui a un très bon ratio performance * fonctionnalité/complexité syntaxique. Allez faire du calcul massivement parallèle sur supercalateur avec du python !!! Maintenant on peut faire de l'orienté objet largement suffisant pour le calcul scientifique. Comparé à du C c'est syntaxiquement beaucoup plus lisible et plus simple (après c'est une question de goût). Bref, si tant de gens dans le domaine du calcul scientifique l'utilise c'est qu'il y a de bonnes raisons !
Je prédis que tu vas prédire que je vais predire que tu vas prédire que je vais choisir cette algorithme. Hmm je sens que je vais trop loin, ou peut-être bien que non ?
Les lapins ne peuvent choisir d'algorithme leur garantissant la victoire pour la raison invoquée dans l'épisode: tout simplement car si le SF connaît cet algorithme utilisé par les lapins, il peut utiliser l'algo qui renvoie toujours la couleur opposée pour choisir les couleurs. Mais le même raisonnement montre que le SF ne peut pas non plus choisir d'algorithme lui garantissant la victoire (si les lapins connaissaient cet algo, ils pourraient répondre toujours juste). Il s'agit donc d'un problème de théorie des jeux sans stratégie gagnante à coup sûr pour l'un ou l'autre parti.
Moi je dis, les lapins de mettent côte à côte, les premiers lapins font en sorte que les blancs soient d’un côté et les noirs de l’autre. Puis les lapins suivant se glissent entre les lapins au milieu de la bande. Les précédents sauront quel chapeau ils portent quand le suivant se mettra à leur gauche ou droite
ça m'a perturbé à la fin je m'attendais à ce que tu dise "la dernière fois..."
+1
J'ai été choqué par la fin abrupte de cette vidéo !!
Pour moi le paradoxe résidait dans le fait que le fameux algorithme du suprême fasciste était dans la liste des lapins mais que puisque l'algorithme donne toujours l'inverse de la prédiction, alors le lapin est indécis sur le choix qu'il ferait car si il dit une couleur l'algorithme donnera forcément la couleur inverse mais il le sait puisqu'il connait l'algorithme. J'avais donc trouvé que les lapins sont voués à perdre mais pas pour la bonne raison ^^
Bien j'avais pensé à la même chose
De même. Car la temporalité n’était pas prise en compte par les Lapins et le Fasciste pouvait gagner sur les coups suivants. Ce paradoxe n'est pas solide dans le sens où il n'y a pas qu'une seule réponse... Mais en fait si, car la stratégie des Lapins n'est même pas applicable. Donc, nous arrêtons le raisonnement à cette étape, avant même de passer au tour du Fasciste. CQFD.
Moi j'ai un petit problème avec l'algorithme du Suprême Fasciste : il est impossible de faire une prédiction sur un algorithme qui ne se finit pas. Donc il sera bloqué avant les lapins pour choisir une couleur, donc il ne pourra jamais coiffer une infinité de lapins, donc nous sommes en face d'un pat mathématiques, non ?
En partant de l'hypothèse que le sf connait la méthode utilisée par les lapins ... ça implique qu'il connaît l'ordre de algorithmes pour vous?
@@LeFerrovipatheEtModeliste exactement.
Et si le chef suprême tire à pile ou face la couleur du chapeau, les lapins n'ont aucune chance de gagner si ?
C'est tout à fait vrai !
En revanche, il est précisé dans l'énoncé que le suprême fasciste ne peut que faire des calculs que les machines de Turing savent faire. Or, une machine de Turing ne sait pas "utiliser du hasard". Donc le suprême ne peut pas lui non plus faire usage de hasard pour déterminer la couleur du chapeau duquel il coiffe un lapin.
@@tristannemoz7277 meme avec un ordinateur quantique? il me semble qu'Alain Aspect explique qu'ils ont des random calculator number quantique deuisdes décénie ;)
@@myfreedom42 un ordinateur de quantique n'est pas une machine de turing. Une machine est dite de turing lorsqu'il y a un bijection entre cette machine et une machine a ruban de turing
@@tristannemoz7277 Merci pour l'explication
Bah en soi une pièce ne sera jamais " parfaite " donc il sera toujours possible de réaliser une algorithme de (machine learning par exemple) capable de prédire les prochains lancer de piècesen fonction des lancers précédents
Lapins : Haha axiome du choix go brrrr
Désolé, pas d'axiome du choix le lundi
Ce meme est tellement stupide et le sujet tellement complexe que ça m'a fait rire
xD
Merci Lê d'aborder des problème de fond comme ça. Mon lapin a lui même été tué par un suprême-fachiste qui voulait lui mettre un chapeau, maintenant sa voix est entendue
Bonjour, est-ce qu'il serait possible d'avoir la référence vers le papier de Chiffaudel qui y fait référence ?
En particulier, il est possible que mon raisonnement soit erroné, mais il me semble qu'ici tu as juste montré qu'il n'est pas possible de les ordonner par taille. On pourrait très bien les ordonner autrement.
Par exemple, on pourrait les énumérer de la façon suivante : Machines de Turing à n états qui s’arrête en n étapes ou moins.
Alors dans ce cas, le problème de l'arrêt n'est plus obstacle puisqu'il sera impossible de dire si la machine n'a pas encore été énumérée par qu'elle ne termine pas, ou si c'est parce que la longueur de son exécution n'a pas encore été atteinte.
C'est le même argument que la diagonale de Cantor sur les nombre reels calculables?
Ils sont "listables" (denombrables) car correspondant a un algorithme. On pourrait faire un algorithme diagonal qui change un chiffre pour chacun dans la liste. le nouveau nombre est calculable par cet algorithme mais n'est pas dans la liste.
Mais si un des algorithmes lapins ne se termine jamais et qu'on attend jusqu'à la nuit des temps... Du coup ils ne peuvent plus fairfe d'erreurs, donc pas d'infinité d'erreurs, donc ils ont gagné quand même ^_^ ?
le probleme reside dans le fait que l'infini se contient lui meme, après une infinité de temps (ce qui n'est normalement pas faisable car l'infini n'est pas un nombre), les algorithmes n'auront toujours pas finit car ce meme temps infini est contenu dans le temps de calcul des algorithmes (voilà pourquoi les raisonnements de type "en fin de compte" ne marchent pas, il n'y a pas de fin et les raisonnements ensemblistes ne s'appliquent pas)
@@serious-goober D'après le définition du problème, peu importe que ça finisse. Si un des algo bloque, et ce sera le cas, alors ils cesseront de faire des erreurs, et donc il y en aura une quantité finie : Les lapins ne peuvent plus jouer, et donc ne peuvent pas perdre (càd continuer de faire des mauvaises prédictions), or c'est tout ce qu'on leur demande (pas de gagner, càd faire uniquement des bonnes prédictions à partir d'un certain rang)
Donc je pense qu'il a raison !
J'ai eu le même raisonnement, les lapins ne feront pas une infinité d'erreur... Il ne perdront jamais. Même si ils ne gagnent pas pour autant.
Match nul ?
@@edwinvital1206 Un drôle de jeu, où pour gagner il ne faut pas jouer.
Les lapins sont obligé de répondre en un temps fini sinon il suffit de ne pas répondre pour gagner
Bonjour, merci pour les vidéos. Bonne vacances.
😂😂😂 t pressé ?!
@@aaronaaron5013 moi, pas du tout. Mais pour lui, oui je suis pressé.
Il faut prendre des vacances vite et longue. Il y a déjà 300 commentaires sur la vidéo. Je sais pas combien de temps on peut passer sur une chaise longue le temps de lire sa.
En tout cas encore bravo pour les vidéos
@@vivelavie858 loool non je plaisante c'est juste que ça m'as fais sourir ton commentaire genre "bonjour, merci, bonne vacance" 😂😂 comme si tu étais entrain de courir et que tu t arreter 3 secondes pour dire ça et repartir looooool
@@aaronaaron5013 c'est pour être gentil.
Le suprême facsiste, le retour :O ! quels souvenirs, j'ai cru être en face de la série Inifni !
Super le retour sur la série Bayes :)
question quand on utilise une commande 'random' dans le langage de programmation, c'est tj algorithmique?
Oui. La commande "random" ne donne pas un véritable nombre aléatoire, elle suit un algorithme déterministe pour générer un nombre pseudo-aléatoire.
8:08 : Le changement d'algorithme est aussi un algorithme.
(et récursivement, un algorithme de changement d'algorithme de changement d'algorithme est un algorithme, donc est dans la liste)
édit : bon, donc en fait, les 2 arguments étaient mauvais.
j'ai pensé exactement pareil ;)
Oui, pareil.
pareil et je me suis même dit que ça allait accélérer le processus puisqu'au début les lapin ont tous faux
@01:40 "tous les livres d'informatique en langage Fortran" : Tant que c'est pas du COBOL...
Ou du Brainfuck...
Windev...
@@mastersoldi3 T'as jamais codé en COBOL pour dire ça ! Windev c'est un rêve à coté !
@@nonothebot arbre programmatique arbre programmatique arbre programmatique .... raaaah
@@ggldmrd5583 brainfuck c'est juste de l'assembleur pour un ruban de Turing…
J'ai une vrai question, pourquoi le terme de "suprême fasciste" est utilisé dans certains problèmes de maths que présente science4all (dans sa vidéo sur l'axiome du choix c'est le cas également il me semble), je me doute que c'est surement ceux qui ont conçu ces problèmes qui ont utilisés ces termes mais je me demande sincèrement pourquoi ? (c'est une histoire de private joke de matheux ?)
Je crois qu'il a répondu à cette question à la fin de l'épisode 16 de sa série sur l'infini, celui sur la diagonale de Cantor.
C'est une généralisation du jeu d'Eleusis non ?
Bonjour Lê,
Je dois dire que ce problème me perturbe depuis quelques jours. Si j'ai bien compris, le fasciste choisie une fonction allant des entiers vers l'ensemble {noir;blanc} (quand je parle de fonction je parle de quelque chose d'équivalent à une lambda). L'algorithme implémentant cette fonction doit s'arrêter pour tout entier. L'ensemble des fonctions prenant en entré un entier et s'arrêtant pour tout entier ne peut être construit algorithmiquement à cause du problème de l'arrêt.
Par contre l'ensemble des fonctions prenant en entré un entier lui peut être construit et il est possible de lui trouver un ordre total. Il est donc possible d'associer un entier à une fonction, et un couple d'entier peut représenter une fonction et l'argument à évaluer.
La stratégie des lapins consistait à évaluer séquentiellement chaque fonctions qui s'arrêtent avec différents arguments. Avec l'ensemble que je propose ce serait une mauvaise idée de faire la même chose puisque parmi les fonctions de mon ensemble certaines ne vont pas s'arrêter avec certains arguments. L'idée serai donc d'explorer de plus en plus profondément chacune des fonctions de mon ensemble.
Pour cela je peut passer par un interpréteur qui prend deux argument arg1:un entier représentant la fonction arg2:le nombre d'instruction/étape que je souhaite réalisé. l'interpréteur donne en sortie une liste. Les élément de la liste de retour représentent les retours de la fonction arg1.
Cet interpréteur est un peu spécial puisque il attribue lui même les entrés de la fonction qu'il interprète.
l'interpréteur initialise la liste de sortie avec une liste vide
L'interpréteur commence par interpréter la fonction arg1 avec 0
il effectue k1 opération et arg1 s'arrête
l'interpréteur ajoute le retour de arg1(0) à la liste de sortie
L'interpréteur commence par interpréter la fonction arg1 avec 1
il effectue k2 opération et arg1 s'arrête
l'interpréteur ajoute le retour de arg1(1) à la liste de sortie
L'interpréteur commence par interpréter la fonction arg1 avec 2
il effectue k3 opération et arg1 s'arrête
l'interpréteur ajoute le retour de arg1(2) à la liste de sortie
...
L'interpréteur commence par interpréter la fonction arg1 avec n
il effectue kn opérations et k1+k2+...+kn=arg2
l'interpréteur renvoie la liste de sortie
Dés lors je propose comme stratégie pour les lapins:
solution_trouvé := Faux
la_meilleur_fonction := 0
iteration := 1
tant que non(solution_trouvé) faire:
f:=0
tant que non(solution_trouvé) et f
Avec un coup de diagonale de cantor on peut pas montrer que l'ensemble des suites de chapeaux possible est indenombrable ? Et du coup les lapins ne peuvent même pas mettre en place leur stratégie ?
Quelqu'un peut il m'éclairer si je fais une erreur ? (Je pense a l'épisode de s4all sur la diagonale de cantor justement)
Il me semble qu'on s'intéresse uniquement aux suites de chapeaux calculables ici puisque le suprême faciste comme les lapins génèrent les suites algorithmiquement
Indénombrable au sens classique
@@zedzed3533 d'accord merci je crois que je vois la différence :)
Ces vidéos sur les fondements des sciences me font kiffer grave
Fortran de retour! Enfin, une partie de mes études pourrait servir. (Ben oui, je ne suis pas né de la dernière pluie, ni de l'avant-dernière d'ailleurs.) :-)))
Les lapins n'ont pas besoin de savoir si un algorithme termine mais uniquement si il termine aussi vite que celui du suprême fasciste. Ainsi, dès que l’exécution d'un algorithme de la liste des lapins prend plus de temps que l'attribution du chapeau, il est tracé et on passe au suivant.
@Iannis Toussaint l'algo 3 est aussi dans la liste des algo.
@Iannis Toussaint On parle de "simples" machines de Turing, il n'y a pas de raison que le même algorithme puisse avoir plusieurs temps d'exécution (l'aléatoire "pur" n'est pas autorisé). Le temps étant relatif au nombre d'étapes de l'algorithme.
Et effectivement, comme le dit Paul Amblard, l'algorithme 3 sera dans la liste. Si on admet qu'on peut faire "attendre" un algorithme, c'est qu'une instruction nous permet de le faire, toutes les "attentes possibles" sont donc listées, comme le seraient d'autres instructions. L'algorithme 3 de votre exemple est donc bien distinct du 1.
La liste de 8puissance 8 ne constitue tu telle pas le nombre maximum d'essai / erreur des lapins ?
Rien à voir avec le fond mais les sous-titre en français autogénérés par youtube affiche « La thèse de flirt sur ring » pour « la thèse de Church Turing ». Entre autre variations de transcription des noms (parfois les mêmes de manière différentes). C’est mignon.
Pour les non avertis, pourriez-vous donner un exemple d’algorithme qui tournerait à l’infini?
Vous pouvez imaginer l'algorithme suivant.
Prenez n'importe quelle conjecture non résolue (Riemann, Syracuse, Goldbach, nombres premier jumeau), puis cherchez un contre exemple et essayant toutes les possibilités.
L’algorithme s'arrête quand vous trouvez un contre-exemple. Mais si l’algorithme ne s'arrête pas, vous ne pouvez pas savoir si c'est parce qu'il n'existe aucun contre-exemple, ou si c'est parce que celui-ci est tellement grand que vous ne l'avez pas encore trouvé.
i=0
k=0
tant que k
un petit cours sur la mesure prochainement ?
10:22 "il est algorithmiquement impossible de construire une liste de tous les algorithmes qui terminent toujours". Il me semble que c'est possible justement, car si j'en crois Wikipédia (source : fr.wikipedia.org/wiki/R%C3%A9cursivement_%C3%A9num%C3%A9rable), "l'ensemble des programmes informatiques qui s'arrêtent est un ensemble récursivement énumérable". Du coup, même si l'arrêt est certes incalculable (on ne peut pas prédire si un algo donné va s'arrêter), j'ai l'impression que ce n'est pas grave pour les lapins, qui ont simplement besoin de la propriété "récursivement énumérable" car elle leur permet de lister, via un algorithme, tous les algorithmes qui s'arrêtent toujours (et donc utilitables par le super-fasciste), jusqu'à trouver en trouver un qui corresponde aux données précédemment acquises. Du coup j'ai l'impression que contre-argument contre les lapins est faux, mais je serais ravi de comprendre en quoi je me trompe si c'est le cas.
Je ne suis pas du domaine mais voici ma compréhension.
Les programmes qui terminent et ne prennent pas d'argument sont effectivement récursivement énumérables, avec une astuce. L'astuce est de générer la liste de la façon suivante: tester tous les programmes de longueur au plus N, mais en les laissant tourner au maximum N étapes. Si un programme s'arrête avant N étapes, l'ajouter à la liste, si il prend plus que N étapes on l'arrête et on passe au programme suivant. Puis quand on a fini de tester tous ces programmes, incrémenter N, et on recommence tout cette fois pour N+1. Continuer pour N de 0 à l'infini. Eventuellement, tous les programmes qui terminent finiront par être listés (à l'étape max(L,T) où L est la longueur du programme et T son temps d'exécution).
La subtilité est que le programme du diable prend un argument, disons i, qui est l'indice du lapin actuel.
Or, l'ensemble des programmes qui prennent un argument i, et terminent pour toute valeur de i, ne semble pas être récursivement énumérable. Je n'ai pas de source pour cette affirmation, mais il y a deux choses qui me font penser que c'est le cas.
Premièrement, on voit que la méthode précédente ne marche plus du tout si il y a un argument (même si on se mettait à tester tous les arguments jusqu'à N - les programmes pourraient terminer en un nombre d'étapes variable dépendant de l'argument), or c'est la preuve que j'ai trouvée en cherchant l'affirmation Vikipédia, j'en déduis donc que Wikipédia part du principe que les programmes sont sans argument, et donc que les programmes avec argument sont de nature différente.
Deuxièmement, j'ai trouvé sur Stack Exchange une preuve que l'ensemble des combinaisons { P, i : P programme prenant un argument, i argument } telles que P(i) termine, est récursivement énumérable. Autrement dit, on peut lister les programmes qui terminent pour une valeur de l'argument fixé. J'en déduis donc qu'il n'est pas possible de le faire pour tout i, sinon l'énoncé aurait pu être simplifié en enlevant i.
Donc en résumé, on peut faire la liste des programmes du diable qui prédiront le chapeau d'un lapin i donné, mais cette liste n'est valable que pour ce lapin. A chaque lapin, on obtiendra une autre liste, ce qui rend impossible la solution pro-lapin.
@@SaiphxXx En effet c'est un bon point, je n'avais pas pensé au problème des arguments. PS je suis contente que quelqu’un ait lu mon argument ! Je ne m'attendais pas à une réponse des années après ! Merci !
Est-ce qu'on ne peut pas utiliser un argument type diagonale de Cantor pour réfuter l'argument pro-Lapin ? Ne peut-on pas parler d'un algorithme qui diffère du premier algorithme à sa première sortie, du second à sa seconde sortie etc. Ce qui donnerait quelque chose d'inédit. Parce que le "suprême-fasciste" peut lui aussi, au fur et à mesure, parcourir une liste d'algorithme et prendre systématiquement l'inverse de sa n-ème sortie. Et si jamais un algorithme prédisait les réponses du "suprême-fasciste" et que cet algorithme était dans la liste à une position m, alors à la m-ème sortie l'algorithme du "suprême-fasciste" différerait. Ça ne me semble pas violer la thèse de church-turing ?
Donc ce n’est pas un algorithme. On ne pourrait pas mettre en pratique ce pseudo-algorithme, parce qu’il faudrait pouvoir dire si un algorithme va s’arrêter ou non.
Salut , quelqu'un peut me faire comprendre pourquoi l'ensemble des suites que peut faire le suprême fachiste par les suites de chapeaux est dénombrable ? est-ce que l'ensemble des suites à valeurs dans {0,1} est dénombrable ?!
Non, l'ensemble des suites à valeurs dans {0,1} est indénombrable.
Par contre, l'ensemble des suites à valeurs dans {0,1} qui peuvent être générées par des programmes, lui est dénombrable.
Car l'ensemble des programmes est dénombrable (on peut lister tous les programmes de longueur 1, puis 2, etc.) donc son sous-ensemble est aussi dénombrable.
Le paradoxe réside dans le fait que les 2 ensembles ont l'air d'être à peu près aussi grands, or non, le premier est fondamentalement plus grand que le deuxième.
Très intéressant comme d'hab. Juste une petite remarque, est-ce qu'on ne pourrais pas dire que la question n'existe pas car il y a une infinité de lapin et que donc on ne pourra jamais vérifier algorithmiquement si ils gagnent ou pas.
PS : C'est quoi cette fortranphobie primaire ? #FortranLivesMatter
d'autant plus que le fortran est vraiment chouette (et tellement bien que depuis qu'on nous prédit sa mort il est encore plus vivant que jamais là où les modes passent)
J'ai adoré cette video. Mais elle me fait poser une question: si les lapins tombent par magie sur la liste des algorithmes qui terminent (on sors un peu du cadre mais tant pis), puis qu'on écris un algorithme qui utilise cette liste pour être différent de chacun de ses algorithmes (comme la diagonale de cantor). On construit alors un algorithme qui n'est pas dans la liste, ce qui nie sa dénombrabilité. Donc un sous-ensemble d'un ensemble dénombrable (pas au sens algorithmique) peut ne pas l'être?
ça ne nie pas sa dénombrabilité. ça nie juste que l'algo du SP termine. Du coup dans ce cas, le SP met une infinité de temps à choisir la couleur des chapeaux...
C'était très cool comme épisode ^^
Les probabilités ? Intéressants comme piste. Hâte d'en voir plus.
Pour faire leur algorithme, les lapins doivent savoir si chaque algorithme finit ou pas. Sinon, dès la phrase "while true then loop", leur algo ne donne jamais de couleur de chapeau. Donc les lapins ne peuvent pas construire leur méta-algorithme. D'ailleurs, si on pouvait faire ce genre de truc, on aurait d'autres contradiction, du genre diagonale de Cantor : soit l’algorithme qui donne la couleur opposée du premier chapeau de l'algo 1, puis la couleur opposée du second chapeau de l'algo 2, etc... Cet algorithme n'est pas dans la liste des algorithmes : contradiction.
j'attendais moi aussi l'argument de la diagonale devastatrice de Cantor :/
Tu ne comptes pas les algorithmes qui te permettent de décider quelle couleur attribuer au n ieme lapin mais les suites de chapeaux blancs et noirs. Or toutes ( presque aucune même en un certain sens) ne sont calculables algorithmiquement.
et si c'est un algorithme qui récupère juste des données d'un comportement "réellement" aléatoire ? (comme utiliser des lampes de laves ou "bruit" de l'espace), les lapins ne pourront pas prédire les chapeaux suivants.
Pourquoi il ne les coifferai pas au hasard? Ou si il utilise un algorithme, il peut le changé après n tours et en utilisés un autres puis revenir à du hasard et ce, un infinité de fois
Je ne suis pas sûr de comprendre pourquoi les algorithmes sont dénombrables. On peut écrire une infinité non dénombrable d'algorithmes du genre: je prend un nombre x entre 0 et 1, et pour le lapin n si x^n a comme première décimale un chiffre paire il a un chapeau noire, sinon il a un chapeau blanc. Qu'est ce qui ne va pas dans mon raisonnement?
La plupart des réels entre 0 et 1 ne sont pas obtenables via un algorithme.
Par définition un algorithme est une suite finie d'instructions, parfaitement décrite par une suite finie de 0 et de 1 (donc isomorphe à l'ensemble des entiers N )
Dès lors que SF peut établir un méta-algorithme anticipant toutes les réponses des lapins, il construit donc un nouvel algorithme non contenu dans l'ensemble initial. Dès lors, l'argument des lapins n'est il pas fallacieux car en réalité l'ensemble des algorithmes n'est pas vraiment dénombrable ?
C'est moi ou le 42 milliardième est plutôt 42 millionième? J'dit ça j'dit rien, j'ai pas bac+27 en math...
Les trois zéros manquants sont en fait à droite de l'écran... En dehors de l'image quoi 😋
"Think outside the box" comme ils disent.
Est ce qu'il est possible de faire marcher une stratégie ou les lapins ne prennent non seulement le nombres de lignes du programme mais aussi le nombres d'étapes qu'il faut pour l'exécution de ce programme ?
Non, car même si le programme doit terminer en un nombre fini d'étapes pour chaque lapin, le nombre d'étapes peut quand même croître à l'infini au fur et à mesure que les lapins augmentent. Par exemple, un programme qui fait N étapes où N est le numéro du lapin dont on décide le chapeau
@@SaiphxXx pourtant ça c'est bien une façon dénombrable de lister tous les programmes qui terminent:
(cette stratégie ne marche que s'il existe qu'un nombre fini de programmes qui s'écrivent en une ligne sur python)
On prend l'ensembles des programmes qui s'écrivent en une ligne sur python, on les faits marcher tous, mais seulement pour une étape de calcul, puis la on teste ceux qui se sont arrêtés après une étape
Si aucun de ces programmes ne marchent on prends ceux qui ne se sont pas arrêtés et on les fait s’exécuter pour encore une étape, et on refait le processus
On teste avec dans l'ordre les programmes de :
1 ligne arrêtés après 1 étape
1 ligne et 2 étapes
2 lignes et 1 étape ,
2 lignes et 2 étapes
1 ligne et 3 étapes
2 lignes et 3 étapes
3 lignes et 1 étape
3 lignes et 2 étapes
3 lignes et 3 étapes
1 ligne et 4 étapes
etc.
Je n'ai pas été convaincu par l'argument, pour le contourner ne suffit-il pas pour les lapins de simplement modifier leur manière de lister les algorithmes ?
Par exemple, si au lieu de lister les algorithmes par la taille de leur code, les lapins listaient les algorithmes par le nombre d'instructions effectivement exécuté, alors les lapins ne resteraient plus bloqués à tester des algorithmes au temps d'exécution infini. De plus ce classement des algorithmes en nombre d'instructions effectivement réalisé peut se faire algorithmiquement, au début de la liste on mettrait par exemple les algorithmes qui s'exécutent en 1 instruction, on sait dès lors que l'algorithme a forcément un nombre d'instructions inférieur ou égal à 1 (si ça n'était pas le cas cela signifierait que certaines instructions ne sont pas exécutées auquel cas, elles n'ont pas à être prisent en compte). Si des algorithmes de 1 ligne exécute plus d'une instruction on peut alors le mettre de côté pour plus tard, lorsque l'on passera aux algorithmes qui nécessitent l'exécution de 2 instructions pour arriver à terme, il suffira d'abord de continuer l'exécution des algorithmes de 1 ligne qui n'avait pas fini de s'exécuter, en gardant de côté ceux qui n'ont toujours pas terminé après 2 instructions avant de faire de même avec les algorithmes de 2 lignes. De cette façon les lapins ne resteront jamais bloqués avec les algorithmes au temps d'exécution infini, car ceux-ci resteront tout simplement indéfiniment de côté.
De mon point de vue les lapins ne vont pas réussir, mais pour une autre raison, dans leur stratégie, ils supposent que le suprême fasciste a un algorithme avec un nombre d'instructions bien déterminé, or, il suffit comme dans la vidéo que le suprême fachiste enrichissent son algorithme avec les réponses des lapins (avec par exemple un algorithme d'apprentissage) pour que la stratégie des lapins tombent à l'eau, de mon point de vue, c'est ici que réside l'erreur de raisonnement des lapins, l'algorithme du suprême fachiste s'enrichit continuellement de nouvelle instruction, donc même si les lapins testent toujours plus d'algorithme différent, ils ne trouveront jamais celui utilisé par le suprême fachiste tout simplement, car celui-ci se complexifie et s'enrichit au fur et à mesure des réponses des lapins (de la même façon que l'algorithme des lapins s'enrichit des choix de chapeau du suprême fachiste).
Le problème avec la stratégie "lister par nombre d'exécutions executées" est que le nombre d'instructions exécutées peut dépendre de l'argument en entrée (numéro du lapin), et qu'il peut augmenter à l'infini. Par exemple, voici un programme qui défait ta stratégie:
def choisir_chapeau( N ) :
i=0
while i < N+1:
i = i + 1
return 0
Ce programme ne sera jamais dans ta liste
On dirait un argument de type diagonale de Cantor mais pour la calculabilité (l'algorithme du suprème fascite qui consiste à répondre le contraire de l'algorithme des lapins ne peut pas être dans la liste que suivent les lapins).
Je crois qu'on oublie souvent les implications du tier-exclu et la force que représente la négation en logique tel qu'on nous l'apprend, après tout la démonstration par l'absurde est souvent le chemin qu'on aime prendre par défaut même quand ce n'est pas nécessaire
Je me suis fait la même réflexion à propos de la diagonale
Je pense que de toute façon, le suprême fasciste n'aura pas le courage de réécrire tout les livres d'info en Fortran donc au pire on perd une infinité de lapin ...
Ouah merci pour ces découvertes des maths constructives !
D'ailleurs peut-on vérifier les théorèmes de la théorie des ensembles algorithmiquement, comme on le fait avec le langage coq pour les maths constructives ?
Si ce n'est pas le cas, les maths de la théorie des ensembles sont assez subjectives...
Interessante video.
En effet l'algorithme des lapins ne termine pas et donc ne marche pas. Cela dit, l'algorithme du supreme ne termine pas non plus, donc ca n'est pas une preuve que les lapins sont sauvés (bien qu'a mon avis, on ne peut pas les sauver, mais je n'ai pas de preuve).
Il me semble que si tu enleves la restriction a la logique constructiviste, les lapins sont sauvés si et seulement si tu as l'axiome du choix (pas 100% sûr à propos du "seulement si").
Dans tous les cas, ca semble difficile que dans notre univers, les lapins puissent etre sauvés, parce que ca voudrait dire qu'ils voient l'avenir. Donc avoir une theorie mathematique (que l'on suppose valide pour notre univers) qui permette de sauver les lapins me semble difficile a concilier avec une vision classique causale du monde. Meme dans un univers purement deterministe comme presenté dans ce probleme, le determinisme de l'univers depend de variables que l'on ne connait pas. En tous cas, ca serait terriblement contre-intuitif et les implications seraient tres interessantes si en effet, les lapins pouvaient gagner (dans un modele mathematique qui corresponde a notre univers).
Ah mais en fait, en y réfléchissant, est-ce que le supreme connait l'algorithme des lapins? Dans la video, il semble que oui, et dans ce cas, évidemment que l'algorithme du supreme va terminer et qu'il va gagner. Quand je dis que je n'ai pas de preuve que le supreme gagne, c'est dans le cas où le supreme ne connais pas l'algorithme des lapins.
Ni les lapins ni le suprême fasciste ne peuvent avoir une stratégie qui fonctionne toujours, dans un univers régit par la loi de Church-Turing. En effet, par l'absurde, si l'un des deux a une stratégie gagnante, cette stratégie gagnante est un algorithme, et cette stratégie gagnante doit fonctionner peu importe l'algorithme qu'utilise l'adversaire. Or l'adversaire peut tout à fait utiliser l'algorithme contraire (pour le suprème fasciste) ou le même algorithme (pour les lapins), et gagner, ce qui est absurde. Aucun des deux groupes n'a une stratégie gagnante.
@@VeganCookies Bah, ca depend de qui connait quoi dans la definition du probleme.
- Je pense qu'il est clair que les lapins ne connaissent pas l'algorithme du supreme. Sinon, il n'y a aucune raison d'énumerer les algorithmes, les lapins gagnent toujours.
- Est-ce que le supreme connait l'algorithme des lapins ou pas? A 7:20 Lê dit que oui, donc admettons que oui.
Dans l'exemple que tu donnes, tu dis que la strategie doit etre gagnante peu importe l'algorithme qu'utilise l'adversaire, mais ca n'est deja pas du tout le cas si il y a une asymétrie dans l'information, telle qu'elle est présentée ici. Ici tu supposes que les lapins connaissent la strategie du supreme, et je suis a peu pres sur que ca n'est pas le cas.. Il me semble que tu fais plutôt reference à des équilibres de Nash, mais ca s'applique quand les 2 joueurs connaissent la strategie de l'adversaire.
@@myrhev42 Je ne suppose pas que les lapins connaissent la stratégie du suprême, ni que le suprême connaît la stratégie des lapins. Mon commentaire s’applique dans ce cas.
Si le suprême connaît la stratégie des lapins, alors effectivement il gagne de toute façon, puisque la stratégie des lapins doit être un algorithme qui termine, il peut donc prendre à chaque fois la valeur inverse. Je n’avais pas pensé au problème de cette façon.
Pour n'importe quelle combinaison de chapeau, l'algorithme du super-faschiste peut forcément se rapporter à :
- choisir un nombre réel
- le transposer en base 2
- assigner à chaque lapin un chiffre (le premier lapin à le premier chiffre, le 2ème lapin à le 2ème chiffre, etc.)
- si le chiffre du lapin est 0 alors il a un chapeau noir sinon il a un chapeau blanc
Or il y a une infinité de nombre réel
Donc les lapins se tromperont forcément une infinité de fois
(Je sais pas si mon raisonnement est bon mais c'est la première chose qui m'est venu à l'esprit)
Hum il pourra uniquement prendre des nombres réels calculables algorithmiquement. Cela fera une infinité dénombrable (au sens classique) de nombres réels que les lapins pourraient énumérer s'ils se bornaient aux algorithmes valides et donc à un moment ou à un autre tomber sur celui-ci ce qui comme le montre la vidéo n'est pas possible
Attention, il me semble que "algorithme" est définit comme terminant. Je pense qu'il ne faut pas utiliser le terme "algorithme qui ne termine pas"
Mais y'as pas moyen de simplement attribuer les chapeaux au hasard? Genre disons en mesurant l'état quantique d'une particule avant d'attribuer un chapeau. Tu arrives à un résultat où les lapins peuvent avoir raison très fréquement parce qu'ils arrivent à deviner la distribution des probabilité des états quantiques de cette particule mais ne peuvent pas garantir une bonne prédiction et sont donc garantis de se tromper de temps en temps.
Pas dans ce cadre là puisqu'on travaille avec des algorithmes déterministes
@@zedzed3533 Bah l'algorithme est déterministe. c'est une simple mesure avec "si A => alors B" "si non-A => alors C". C'est le monde qu'on mesure qui n'est pas déterministe =p
Après tu peux ajouter ça comme exception à ton expérience de pensée mais ça commence à faire pas mal de règle arbitraire, déjà qu'on doit imaginer une infinité de lapin y'as un moment ton expérience de pensée veut plus rien dire. Si on éliminie les solutions au problème en ajoutant une règle arbitraire qui les interdit c'est assez facile de créer des tas de problèmes impossible à résoudre.
@@Laezar1 Tu pars du principe que les seuls données que tu connais ce sont les lapins et leurs couleurs de chapeaux après si tu changes les règles tu peux faire beaucoup de choses
@@zedzed3533 Bah il s'agit juste de savoir si il y à un algorithme qui même une fois connu peut générer une infinité d'erreur, y'a à priori aucune limitation sur ce qu'on peut inclure dans cet algorithme.
Ou alors fallait rajouter les règles dans l'énoncé.
@@Laezar1 Tes seuls données ce sont un sf, des lapins et des chapeaux le reste tu sors du cadre du problème
pas de maths non-constructiviste = pas de raisonnement par l’absurde par exemple ? (en tout cas certains)
Avant de voir la réponse :
J'avais déjà réfléchis à un paradoxe semblable impliquant les conséquences du fait que le comportement humain serait prévisible (dans le sens ou il serait possible de connaître avec une précision satisfaisante le comportement d'un humain dans un court laps de temps)
Dans ce cas il serait possible de faire une machine qui prévoit le comportement d'une personne avent que celui-ci ai lieu, mais comme condition il doit le montrer à la personne
Seulement que cette personne est rebelle et veut faire mentir la machine, du coup quel que soit la prédiction que fait cette machine, il veut la faire résulter fausse , et la machine connait ce paramètre sur les facteurs influençant le comportement de cette personne
Du coup comment va se comporter le système machine-personne?
Superposition des prédictions ?
J'ai l'impression que Lê aussi a réfléchi à ça, étant donné qu'il y a peu il a écrit un article sur une résolution du paradoxe de Newcomb.
@@mamadouharissa9883 je savais pas que ça s'appelait "paradoxe de newcomb", merci
@@chainesciences7125 Mais de rien
Elle calcule qu'il meurt par un rayon laser venu de la machine juste après le début de la prédiction (se faire assommer marche aussi)
Super vidéo ^^
Est ce que cette stratégie marche : (cette stratégie ne marche que s'il existe qu'un nombre fini de programmes qui s'écrivent en une ligne sur python)
On prend l'ensembles des programmes qui s'écrivent en une ligne sur python, on les faits marcher tous, mais seulement pour une étape, puis la on teste ceux qui se sont arrêtés après une étape
Si aucun de ces programmes ne marchent on prends ceux qui ne se sont pas arrêtés et on les fait s’exécuter pour encore une étape, et on refait le processus
On teste avec dans l'ordre les programmes de :
1 ligne arrêtés après 1 étape
1 ligne et 2 étapes
2 lignes et 1 étape ,
2 lignes et 2 étapes
1 ligne et 3 étapes
2 lignes et 3 étapes
3 lignes et 1 étape
3 lignes et 2 étapes
3 lignes et 3 étapes
1 ligne et 4 étapes
etc.
On peut faire ça, et c’est effectivement une manière de lister tous les programmes qui s’arrêtent. Par contre, cela ne permet pas aux lapins de gagner, puisque si le temps que prend la stratégie du suprême fasciste peut croître très rapidement, obligeant les lapins a changé constamment de programmes pour chaque nouvelle étape du jeu.
@@VeganCookies j'étais justement en train de penser à ça et en fait c'est pas nécessairement un problème car les lapins peuvent déjà voir si le programme aurait été bon rétrospectivement entre deux choix, et vu que le programme du suprême fasciste est d'office un programme qui comporte un nombre fini de lignes et un nombre fini d'étapes les lapins vont d'office tomber dessus
mais du coup se pose l problème des programmes dont le temps d'exécution change à chaque fois
*pause à **8:00*
Je pense que l'erreur des lapins est de supposer que connaître l'algorithme suffit. Sauf que pour connaître le résultat d'un algo il faut aussi connaître les paramètres de cet algo, et ça ce n'est pas nécessairement énumérable.
*fin du visionnage*
Ok, effectivement, et dit comme ça c'est tellement gros que je me sens un peu nul de ne pas y avoir pensé^^
J'avais aussi parié sur le suprême fasciste, mais pour une autre raison :
Si on peut supposer que le suprême fasciste peut connaître le plan des lapins, on peut aussi supposer qu'il utilise un algorithme qui utilise comme donnée le choix de couleur que font les lapins, pour déterminer la couleur du prochain chapeau. On peut alors imaginer que l'algorithme du suprême fasciste s'affine en "devinant" quels algorithmes ont été essayés par les lapins. Il a alors en permanence un coup d'avance, car l'algorithme qu'il utilise est forcément plus loin dans la liste des lapins, car il contient, en quelque sorte, les algorithmes déjà essayés.
Bon j'ai mis pause à 8:06. Mais de manière générale c'est l'hypothèse de départ qui est discutable : peut on changer d'algo en cours de route ? Par exemple, le SF , s'il voit que les lapins ont raison plus de x fois, change d'algorithme aléatoirement : alors il y aura forcément une infinité d'erreurs. SI l'algorithme du SF est variable, les lapins finiront en civet et nos programmes en fortran. Pourtant ce changement d'algo... Peut être un algo. Dans ton exemple tu confonds un algorithme avec une séquence de chapeaux : le choix du SF ne dépend pas des réponses des lapins. Par contre le choix des lapins est influencé par les choix précédents du SF. Il n'y a pas une infinité de séquences possibles mais à chaque moment, si le SF change, il y a une infinité de séquences ultérieures possibles. C'est donc la stratégie des lapins qui est basée sur un choix fallacieux, car basé sur le fait que l'algo du SF est en quelques sortes "stable". Et il est facile d'en trouver qui ne le soient pas.
Allez je vais voir la suite, bisous
Edit : Je pense que j'ai tapé pas loin, si je comprends bien les lapinous partaient du principe qu'ils pouvaient lister ces algorithmes, en fait non car il y a justement des algorithmes qui ne s'arrêtent pas (ceux que j'ai proposés et celui que tu proposes aussi en contre exemple sont effectivement des algos qui ne s'arrêtent pas) . Pire qu'absents d'une éventuelle liste, ils ne peuvent juste pas être listés.
Merci en tout cas pour ce noeud cérébral qui va hanter ma semaine ;)
S'il change d'algorithme après un certain nombre d'échecs, les lapins n'auront qu'à trouver dans quel ordre "aléatoire" les algorithmes sont choisis (par un algorithme) et après combien d'erreurs. Le problème, c'est s'il est seulement possible en un nombre fini d'essais de trouver le bon algorithme. Personnellement j'avais pensé que c'était impossible si l'algorithme utilise une seed, alors pour un seul algorithme, il faut tester toutes les seeds possibles, mais étant donné qu'on ne connaît pas la taille de la seed, on ne peut jamais terminer.
@@al8-.W Je dirais oui, en fait dans ce cas on reproduit schématiquement ce qu'il se passe dans le cadre favorable aux lapins mais avec hélas un nombre infini d'erreurs car on remet une pièce à chaque fois que les lapins ont un certain nombre de réussites. Reste sinon au SF à simplement changer d'algo à chaque coup et là la stratégie des lapins, je pense quelle qu'elle soit, ne peut que voler en éclat et nous serons tous condamnés au fortran. Je crois qu'en fait il est facile de trouver des scénarios pour lesquels le SF est imbattable. Après je pars du principe qu'un "nombre fini d'erreurs" se traduit par le fait qu'à compter d'un certain point , les lapins auront toujours raison. Ce point peut ne jamais arriver selon la stratégie d'algos du SF
Les algorithmes finis et infinis sont mélangés. En choisissant comme algorithme les plus courts d'abord mais aussi ceux tournant le moins d'abord, les lapins ne peuvent-t-ils pas parer à la faille? 1 ligne et 1 tour, 1 ligne et 2 tours, 2 lignes et 1 tour, 2 lignes et 2 tours...
Fichtrement intéressant ! ^^
Sans ignorer cette vidéo, je change de sujet: j'ai une question qui me semble assez importante, car je suis à la croisée des chemins, et j'hésite. Quels études à tu fais pour arriver à ce stade de connaissances ? Fac ? Prépa ? Ou juste des livres/vidéos 😅 ? (Et si quelqu'un aurait déjà posé cette question, sur quelle vidéo puis-je trouver réponse ? Merci beaucoup !!!)
Au passage je voudrais te dire que j'adore toutes te vidéos, et que c'est génial d'écouter et de comprendre un passionné !
Bonne journée
Lê est chercheur en maths appliquées. En revanche, je ne connais/souviens pas de son parcours à part qu'il a fait son doctorat en Suisse je crois.
Oh non! Pas du fortran! Tout sauf ça
Du Cobol ?
Du brainfuck? (cf un commentaire que j ai vu ici)
Super vidéo!
En fait, je ne vois rien qui permet d'affirmer avec certitude qu'il existe un nombre fini d'algorithmes décrivant la situation. Après tout n'est-il pas possible de faire en sorte que l'algorithme le plus simple pour décrire la couleur du chapeau soit la liste des couleurs des chapeaux de tous les lapins ? Ces derniers étant une infinité...
Pour moi les lapins sont voués à l'échec car le suprême peut aussi utiliser le hasard plutôt qu'un algorithme.
Dans ce cas, ou bien les lapins devront répondre au hasard mais ainsi feront des erreurs à l'infini, ou bien essayer de déterminer un algorithme (le leur, ou qui un essaye d'en identifier un utilisé par le suprême) mais dans ce cas le suprême prend forcément l'avantage, comme dit dans la vidéo.
Mais la solution pour les lapins réside peut-être dans la notion d'infini. Les lapins obligent le suprême à aller jusqu'au bout de l'infini pour qu'il soit sûr qu'à aucun moment les lapins ne "prennent le dessus à l'infini". On parle de compter à l'infini là ! Si les lapins font un gogoplex de succès, le suprême va toujours essayer de chercher sa victoire, et le peut ; si les lapins font un gogoplex de défaites, ils pourront toujours demander à continuer leur chance, et statistiquement ça se pourrait, à l'infini... Ainsi, jamais jamais le suprême ne pourra lui-même venir à bout du défi qu'il a lancé, et les lapins vivront pour toujours sans inquiétude !
Seul Chuck Norris a compté jusqu'à l'infini. Deux fois, dont une en partant de la fin.
Je ne comprend pas bien la non-denombrabilité des algorithmes qui terminent :
Étant donné une énumération de tous les algorithmes, il suffit d'exécuter:
L'instruction #1 de l'algo #1
L'instruction #2 de l'algo #1 et l'instruction #1 de l'algo #2
...
Les instructions #(n-k) de l'algo #k, pour k entre 0 et n : si l'algo #k termine on lui donne une étiquette, et s'il est déjà terminé on le saute.
En procédant ainsi, on va pouvoir "exécuter en parallèle" tous les algorithmes, et ainsi finir par étiqueter tous ceux qui terminent (et donc obtenir un dénombrement sans axiome du choix)
Il me sembleraient donc que seuls les algos qui ne terminent pas sont indénombrables.
Ça va, ça aurait pu être la Cobolpocalypse
C'est tout de suite plus clair que les explications de Sardoche !
Je pensais qu'il était impossible qu'une infinité de lapins se rappellent parfaitement des algorithmes et les exécutent tous dans un temps raisonnable, et ce sans jamais faire d'erreur...
peut-être que la meilleure stratégie pour les lapin est de décider de garder secrète leur stratégie (qu elle qu elle soit). Du coup le seul moyens pour savoir qui gagne sera de mener l expérience jusqu'à l infini alors que chacune des étapes dure un temps non nul... et le monde est sauvé 🥳🥳🥳
je pensais la réponse allait etre quelque chose du type "diagonale devastatrice de Cantor" où les lapins dénombrent un infini mais le diable peut toujours trouver quelque chose qui n'est pas contenu dans cet infini
La meilleure solution pour tuer tuer tous les lapins serait le tirage au sort pour choisir la couleur des chapeaux 🤠. À moins d'avoir l'obligation d'utiliser un algorithme.
Un tirage au sort est un algorithme au final
@@sebastienlecoester4923 la randomisation est une solution
@@stephanedodeuil4655 Pas avec une machine de Turing il me semble
Ca me rappelle un épisode de rick & morty 😅
Le truc du sous ensemble non dénombrable dans un ensemble dénombrable m‘a perturbé jusqu‘a ce que je comprenne que cela veut dire qu’en réalité ce sous-ensemble est bien dénombrable mais qu’on ne peut pas le construire
7:50
Mais... L'algorithme du suprême fachiste pourrait être numéro infini quelque chose, non ? Genre yaurait une infinité de mauvais algorithme avant, donc une infinité de mauvaises réponses...
G une question infini^infini est plus grand que l infini ?
Non, même classe.
Tout dépend ce que tu appelles infini et "plus grand que". En tout cas en mathématiques classiques, IN^IN l'ensemble des applications de IN dans IN a la puissance du continu et est donc de cardinalité supérieure à la cardinalité de IN.
@@edwinvital1206 Plus petit que quoi ? Je ne vois pas où tu veux en venir. Ensuite ben, non, 2^Aleph_n n'est pas nécessairement égal à Aleph_n+1, ça impliquerait en particulier que 2^Aleph_0 = Aleph_1 ce qui est exactement l'hypothèse du continu (est-ce que le cardinal de P(IN) est le plus petit cardinal supérieur au cardinal de IN ?). Or on sait que l'hypothèse du continu est indécidable dans ZF(C).
J'aimerais argumenter que, dans notre expérience, le problème de l'arrêt n'est pas valable, car on suppose les lapins et le SF infiniment intelligents, a minima pour que les lapins puissent trouver en moins de 10 secondes une solution qui peut nous prendre des jours à déterminer.
Or, le problème de l'arrêt demande que une opération, quelque soit sa complexité, ne puisse être résolue qu'en un temps non nul, car il faut qu'il existe un algorithme qui ne boucle pas, mais que sa résolution se fasse sur une échelle de temps qui, à l'échelle de l'observateur, soit assimilable à l'infini.
Sauf que, si les lapins prennent un temps non nul à faire des opérations: soit le SF leur laisse un temps (absolument) infini pour résoudre son problème, auquel cas les lapins ont tout leur temps pour réaliser les algorithmes, et peuvent se permettre d'attendre une infinité de secondes pour essayer de résoudre l'algorithme avant de passer au suivant, (On peut dire que le lapin se pose ꞷ0 secondes avant de déduire que l'algo boucle, pendant que les autres vont faire une sieste chez Hilbert qui a posé son hôtel pas loin), dans ce cas le problème de l'arrêt n'est plus un problème,
Soit le SF laisse un temps T à chaque lapin pour faire un choix, mais le problème est trivialisé car il suffit au SF de choisir un algorithme qui, quelque soit sa manière de le définir, demande un nombre d'opérations supérieur à T/𝜏, avec 𝜏 le temps nécessaire à un lapin pour réaliser une opération, et attendre juste le moment inévitable ou les lapins n'auront pas assez de temps pour résoudre l'algorithme.
Dernier cas, les lapins infiniment intelligents font des opérations en un temps nul, ainsi ils peuvent déterminer instantanément si un algorithme boucle, et le problème de l'arrêt ne se pose plus.
Mon hypothèse c'est qu'on a oublié de préciser que le suprême fasciste doit utiliser un algorithme qui termine et j'ai franchement l'impression que celui là ne termine pas
Spoiler
Ah bah en fait c'est celui des lapins qui ne termine pas
S'il était possible de lister les algorithmes qui terminent, ne serait-il pas possible de battre les lapins avec l'algorithme suivant :
- Le fasciste, disposant également de la liste, utilise arbitrairement un algorithme de la liste pour commencer (disons la liste numéro i)
- si les lapins ont un grand nombre de réussite successives, le fasciste utilise un algorithme pseudo-aléatoire pour récupérer un nouvel indice d'algorithme à utiliser, pour que les lapins recommencent à se tromper
- Les lapins ne peuvent ainsi jamais trouver le bon algorithme, car l'algorithme change quand ils le trouvent
J'imagine que le point faible de cet argument pourrait résider dans la supposition qui existe un algorithme pseudo aléatoire pour ressortir un nombre entre 1 et l'infini. Je ne sais pas si un tel algorithme est concevable (entre 1 et n, c'est possible, mais là j'en ai aucune idée)
Un algorithme pseudo-aléatoire est toujours un algorithme, donc il doit être dans la liste, et donc si les lapins ont accès à la liste, ils finiront pas le trouver et à suivre exactement les changements d’algorithme du fasciste.
Rien compris... 🥺 C'est la première fois que ça me fait ça... Si le suprême machin choisir des chapeaux au hasard,.les lapins ont perdus et on arrête là non ?
Je pense qu'il ne peut pas faire ça car ses choix doivent pouvoir être calculés par la thèse de Church-Turing (donc par un algorithme). Le hasard ne peut pas être "calculé".
le fait de devoir utiliser un algorithme interdit de faire une infinité de choix au hasard. Ici algorithme => pas d'axiome du choix.
J'avais pensé à un autre argument contre les lapins, mais je ne saurais pas dire si il est valide :
Le jeu étant fait en itérations (les lapins se présentent les uns après les autres, et doivent déterminer la couleur de leur chapeau avant que le suivant arrive), le suprême fasciste pourrait se rendre compte que les lapins ont découvert son algorithme et en changer subitement non? Par exemple après un grand nombre de réussite des lapins, ce qui suggèrerait qu'ils sont sur la bonne voie, il peut choisir un tout nouvel algorithme, et ainsi de suite à chaque fois que les lapins ont les longues séries de réussite ( dix, cinquante, un milliard... peu importe).
Sauf qu'il existera un algorithme qui le prédit malgré tout: Si le SF suit l'algorithme A pour les 10 000 premiers chapeaux, mais qu'il décide ensuite de changer pour prendre l’algorithme B, il arrivera un moment ou les lapins atteindront un algorithme que l'on nommera C, qui est {Pour le N-ieme chapeau, si N
Il y a deux éléments qui me perturbent dans cette histoire.
La première est de parler d'algorithmes qui s'arrêtent sensés construire des listes infinies.
La seconde est le problème de la vitesse de calcul.
Soit celle ci est finie auquel cas il n'y a pas besoin de faire la liste des algorithmes s’arrêtant toujours. Il suffit de prendre la liste, dénombrable, de tout les algorithmes, et de ne considérer que ceux qui ont rendu un résultats après n opération (qui peut dépendre du numéro du lapin). Soit elle est infinie et les algorithme ne s’arrêtant jamais s'identifient d'eux même dans la la liste (ce sont les seul à ne pas s’arrêter immédiatement).
Au final, j'ai l'impression que les lapins ne perdent que si le suprême fasciste est le seul à posséder une vitesse de calcul infinie.
J'aurais tendance à quand même faire gagner le fasciste, car si il a accès à la même liste que les lapins, il peut tout à fait changer d'algorithme à chaque lapin pour prendre un algorithme plus loin dans la liste (un revenir sur un algorithme qui aurait donné un résultat erroné sur un lapin déjà venu est aussi un algorithme, par contre je sais pas le placer pour être sûr de rester en avance sur les futurs ragouts).
Personne n'a jamais besoin d'attendre le tirage d'une suite infinie dans l'histoire. Le suprême fasciste peut très bien tirer le n-ième chapeau seulement au moment où le n-ième lapin arrive et les lapins n'ont quant à eux pas la prétention de tirer une suite infinie, mais de tirer une couleur à chaque fois.
Ça aurait pu être pire, ça aurait pu être du Prolog...
Ou du Brainfuck...
Exactement les deux langages entre lesquels j'étais en train d'hésiter.
@@isaacvongurtberg7341 :D
Peu t on faire un nombre aléatoire avec une machine de Turing... (Algorithme du SF)... Sinon, la sequence des lapins antérieur peut permettre de trouver l algorithm pseudo-aléatoire du SF.
@Science4All Mais si les lapins possèdent déjà la réponse, je veux dire, s'ils ont déjà un tableau infini mais déjà construit liants chaque algorithmes avec le fait qu'il finissent ou non ? ils n'ont alors pas besoin d'utiliser un algorithmes pour déterminer quels algorithmes finissent ou non, ils suivent juste leur tableau déjà construit et peuvent ainsi savoir la bonne réponse. Et dans ce cas qui se trompe ? Toujours les lapins ? (remarque peut-être qu'en disant ça je te demande juste : "Et si la thèse de Turing était fausse ?", j'ai du mal a savoir ^^')
Le problème, c'est toujours le même : l'infini.
Notre définition de l'infini, c'est que c'est l'ensemble de toutes les possibilités.
Comme dans les décimales de Pi: parce qu'elles sont infinies, on peut y trouver toutes les suites de nombres possibles.
C'est un problème axiomatique.
Les scientifiques tournent en rond dès qu'il s'agit de l'infini.
Par exemple, la diagonale de Cantor est fausse : la liste de Cantor étant infinie, elle contient tous les nombres possibles .. mais Cantor crée un nombre qui ne peut être contenu dans sa liste ..
C'est un paradoxe !!!
Dès qu'on étudie l'infini, on aboutit à plein de paradoxes !!
D'après le théorème d'incomplétude de Godel, notre système axiomatique est faux: notre définition de l'infini est fausse.
Mais les gens comme Lê préfère continuer à tourner en rond, comme avec ce genre de vidéo ..
♉♉♉
+1000
Un autre paradoxe qu'on obtient en faisant des calculs avec des infinis c'est la fameuse "somme de tous les entiers positifs qui serait "égale" à -1/12, alors qu'une telle somme devrait "converger vers + l'infini".
C'est pour ça que j'ai toujours considéré que chercher à utiliser l'infini dans un calcul mathématique c'est aussi insensé que chercher à utiliser Dieu comme paramètre dans une équation de physique : ça part très vite en cacahuète.
Je pense que vous regardez trop de vidéos vulgarisatrices de maths ... L'infini est très bien cadré en mathématiques, ce que dit Lê peut être décrit très formellement sans aucun paradoxe et ne tourmente aucun mathématicien... d'ailleurs il n'y a pas de paradoxe puisque le raisonnement des lapins est faux ... quand à la somme 1+2+3+... qui vaut -1/2 , je ne sais pas quelle vidéo à sensations vous avez vu mais c'est un abus de notation énorme valide uniquement dans un contexte particulier où l'addition n'est plus du tout ce que vous croyez (c'est même mensonger d'utiliser le signe "+" ). Dans la formule 1+2+3+... les nombres 1,2,3 ne sont pas des nombres et le symbole "+" n'est pas l'addition, et -1/12 n'est pas non plus le nombre -1/12 ... Pour écrire 1+2+3+... = -1/12 formellement on doit d'abord faire 10 pages de définitions et redéfinir absolument tous les symboles usuels, en particulier on doit définir la fonction zéta de Riemann et autres bizarreries juste pour pouvoir décrire ce fameux "+", ce qui requiert au moins des maths BAC+2, donc ce "+" n'a VRAIMENT rien à voir avec l'addition... Si quelqu'un vous a prétendu que 1+2+3+... = -1/12 sans vous préciser que + n'est pas l'addition dans cette formule c'est soit qu'il n'a rien compris non plus soit qu'il veut vous tromper purement et simplement. C'est comme si je disais qu'à partir de maintenant je note la multiplication avec le symbole + et que je vous dis "3 + 3 = 9 !!!! incroyable" mais sans vous préciser ce que signifie mon "+". Dans les notations usuelles où 1,2,3 sont des nombres entiers la série 1+2+3+... diverge vers +l'infini et personne ne conteste ce résultat.
@@SaiphxXx
Vous voyez, vous le constatez par vous même : vous écrivez vous même que tout dépend de nos définitions.
Le signe + ou ×: vous utilisez cet exemple. ( 1+2+3 ... =-1/12; c'est la somme de Ramanujan, Lê a fait une vidéo sur le sujet)
Vous prenez un autre exemple pour dire la même chose que moi: tout dépend de la définition que l'on donne à quelque chose.
C'est un problème axiomatique.
Le problème, c'est la définition de l'infini en mathématiques ..
Ce n'est pas sur les calculs que les scientifiques bloquent ; ils bloquent sur la notion elle même de l'infini.
C'est quoi l'infini ? Un ensemble de toutes les possibilités ?
Donc c'est normal que infini=-1/12..
Ou alors, les décimales de Pi sont infinies, donc infini=Pi ?
La fraction 1/3 est un nombre rationnel .. et pourtant les décimales sont infinies 0,3333 ... donc infini=1/3 ?
Alors oui, de nos jours, on est capable de démontrer n'importe quoi, comme 1+2+3 ...=-1/12 ..
On est capable de le démontrer en mathématiques !!!!
Ça prouve bien que le problème est axiomatique ..
Le problème, c'est la définition de l'infini ..
♉♉♉
@@pierrestempin100
Somme 1+2+3...=-1/12
Somme 1+1/4+1/16 ..=-1
0,99999....=1
Les décimales de Pi sont infinies ..
1/3= 0,33333 ...
Etc .. etc ...
Donc c'est quoi l'infini ?
Infini=-1/12=-1=1/3=Pi ...????
Pierre, si je vous dis :
un ensemble E, des nombres entiers entre 1 et 9.
1, c'est correct
2, c'est correct
7, c'est correct
Notre définition de l'infini, c'est que c'est un ensemble !!! Un ensemble à l'infini !!!
Donc, comme pour l'ensemble E, je peux dire pour l'infini:
-1/12, c'est correct
-1, c'est correct
Pi, c'est correct
1/3, c'est correct
Vous comprenez Pierre ?
Le problème, c'est qu'à cause de notre définition de l'infini, on peut donner à l'infini n'importe quelle valeur !!!
Et c'est exactement ce qu'il se passe .. on peut démontrer n'importe quoi, ça sera toujours correct !!!
Comme la somme de Ramanujan ..
♉♉♉
@@SaiphxXx
Pour les vidéos et vulgarisations liées la somme des entiers positifs "égale" à -1/12 :
MicMaths a fait une vidéo dessus : th-cam.com/video/vMnkmBCvGQc/w-d-xo.html
Science étonnante a fait un billet de blog dessus : sciencetonnante.wordpress.com/2013/05/27/1234567-112/
Numberphile a fait une vidéo dessus (en anglais) : th-cam.com/video/w-I6XTVZXww/w-d-xo.html
Et ils vont tous dans le sens de "ce résultat incroyable mais vrai" et sans redéfinir le moindre terme utilisé dans l'équation.
Lê aussi a fait une vidéo dessus : th-cam.com/video/xqTWRtNDO3U/w-d-xo.html
et il est le seul à mettre en avant la contradiction 1=0 que montre un des commentateurs du billet de blog de Science étonnante en suivant un tel raisonnement.
A titre personnel, ce qui me dérange, c'est pas tant l'utilisation (non-redéfinie) de l'addition que celui de l'égalité.
Autant je suis prêt à accepter la proposition "la somme de 1 à n TEND VERS + l'infni" quand n TEND VERS + l'infini". J'accepte l'aspect cadrant de l'infini, mais pas son utilisation telle quelle comme nombre ou cardinal au sein d'un calcul.
j'en suis à 8:01 et ça ressemble fortement à du Cantor en binaire, en remplaçant 0 et 1 par noir et blanc. Les lapins ne font que lister les possible listes de et 0 de 1 possible (en passant par les algos qui les créé) sauf qu'il y en a une infinité (dénombrable) le suprême fasciste essaie d'en rajouter une n'étant pas dans la liste. Donc plusieurs possibilité :
1) la liste des lapins n'est pas complète et donc il existe une infinité non dénombrable d'algorithme possible (ce qui est contredit par la thèse de Church Turing)
2) Un algo qui prédit la technique des lapins est impossible.
3) La liste des algorithmes possible n'est pas faisable (mais comme leur infinité est dénombrable...)
bon après j'écris ça à 6h du mat en 5 min donc il y a forcément des erreurs de raisonnement peu être même grossières.
comme quoi ça devient rapidement la merde qu'on essaye de placer des infinis dans calculs
Mais du coup, si le n-ième lapin doit attendre indéfiniment que les algorithmes soient calculés avant de faire sa prédiction, alors il ne fera jamais sa prédiction. Cela implique donc qu'il n'y aura jamais de cas dans lequel il y aura plus de n-1 prédictions effectuées, et donc plus de n-1 erreurs commises.
Le nombre d'erreur des lapins sera donc bel et bien fini avec leur stratégie.
Je parierais sur les lapins : Est-ce que tout ne se ramène pas à une question de "puissance de calcul": les Lapins étant beaucoup plus nombreux (une infinité même ?) Devraient pouvoir créer un modèle du fachiste (par exemple un réseau de neurones) dont la complexité de Solomonof est comparable au cerveau du fachiste. Le fasciste lui, du fait de ses ressources limitées, est incapable de modèliser l'ensemble des lapins avec un niveau de complexité comparable. Les lapins devraient donc être capables de prédire de manière exacte le comportement du fasciste, ce qui n'est pas réciproque.
Je n'ai peut-être pas bien compris les règles de départ, mais pour moi, il me semblait évident que le suprême fasciste ne pouvait pas perdre : il lui suffit de lancer une pièce à chaque nouveau lapin qui arrive. Il donne un chapeau banc si c'est pile, un chapeau noir si c'est face. Puisque la distribution est aléatoire, les lapins auront une chance sur deux de se tromper, ils se tromperont donc en moyenne une fois sur deux. Puisqu'il y a une infinité de lapin, il se tromperont une infinité de fois. Où réside mon erreur de raisonnement ?
3:24 si je comprend bien la thèse de Chruch-Turing, on peut en conclure que, parmi tous les algorithmes existants, il y en aura un qui produira une simulation parfaite de l'univers, et dont le résultat sera si la pièce atterrit sur pile ou face. Donc une fois que les lapins auront atteint cet algorithme, ils en déduiront le résultat du jet.
Et si le suprême fasciste décide de changer de méthode une fois que les lapins ont trouvé cet algorithme, il existe un algorithme qui est comme le premier, mais qui en plus prédit parfaitement le comportement mental du suprême fasciste, cad que l'algorithme prédit les changements d'algorithme du suprême fasciste.
Et si le suprême fasciste change d'algorithme par périodes déterminées par un algorithme ?
Et très bonne vidéo encore une fois !
l'infini car le Lapin détecte la différence ... 9mn40
Comment le faschiste fait-il pour choisir un algorithme ? Il est soumis au meme probleme d'arret que les lapins. Le faschiste doit choisir un algorithme parmi ceux dont il peut calculer qu'ils terminent. Les lapins peuvent donc faire la liste de ces algorithmes la.
Pour presiser mon commentaire peut etre un peu confus : Le sous ensemble des algo qui termine n'est pas denombrable, mais le sous ensemble des algo dont on peut calculer qu'il termine lui est denombrable (enfin c'est mon intuition). Hors c'est parmi ce dernier que le fashiste prend son algorithme.
@@MrDarkPage De une, c'est pas si évident que le suprême fasciste prenne forcément un algorithme qui termine prouvablement. De deux, ça me paraît trèèès peu probable que l'ensemble des algorithmes qui se terminent prouvablement soit algorithmiquement dénombrable.
Si j'étais un lapin je ne m'inquieterai pas
On ne peut pas faire une infinité d'erreurs en un temps fini
Et si j'etais un lapin je ne voudrai pas vivre eternellement
Yo
Dans le cas où le suprême fasciste applique l'algorithme qui consiste à appliquer l'algorithme global des lapins, puis à inverserser la prédiction pour chaque lapin, que se passerait-il dans le cas suivant : cet algorithme du suprême fasciste est le n° 60 000 000 dans la liste des algorithmes des lapins, et tous les algorithmes précédents de cette liste ont terminé. Les lapins ont donc fait 59 999 999 erreurs jusque là. Arrivés au lapin n° 60 000 000, ils font tourner l'algorithme n° 60 000 000, qui est donc l'algorithme du suprême fasciste. Que se passe-t-il alors ? Les lapins peuvent trouver la bonne réponse ? Le suprême fasciste boucle à l'infini ? Les lapins aussi ?
Argument pro-lapin :
Le temps ne peut être mesuré sur des intervals inférieurs au temps de Plank. Il est donc raisonnable de penser que l'échange avec chaque lapin ne peut être plus court que celui-ci. De plus, l'univers à une durée de vie finie (voir th-cam.com/video/11XQUHOU_aw/w-d-xo.html de Balade Mentale). Cela borne le nombre de réponses possibles faites par les lapins à une quantité finie, rendant impossible un nombre d'erreurs infini.
les machines de turing ne sont pas bornées dans le temps ou l'espace
Source de ce que tu avances sur le temps de Planck ? Le temps de Planck c'est juste le plus petit temps faisant sens vis à vis du déplacement d'une particule, mais rien n'indique que toutes les particules de l'univers soient synchrones. Pour parler grossièrement, tu pourrais très bien avoir un atome qui "s'update" tous les t = 0 mod tp et un autre atome qui "s'update" tous les t = tp / 2 mod tp où tp est le temps de Planck, auquel cas ton système évolue avec un pas de tp/2.
@@neloka4313 Je ne pensait pas au temps nécessaire pour choisir la couleur du chapeau mais à celui nécessaire pour échanger l'information entre le suprême fâchiste et les lapins. Puisque ce sont des entités physiquement discernables, elles sont séparée par une certaine distance au moins égale à la distance de plank. Ce fesant, tout transfert d'information met alors un temps de plank pour aller de l'un à l'autre.
@@Naheulf Oui enfin là tu te fais plus stupide que tu ne l'es. :)
en fait voila ce que doivent faire les lapins :
le premier se place
le 2ieme lapin voit un chapeau noir il se place a droite du lapin, si le chapeau est blanc il se place a gauche
le 3ieme et les suivants :
ils regardent la couleur des chapeaux et se positionnent entre les 2 lapins qui ont des chapeaux différents ou bien a droite du dernier blanc ou a gauche du dernier noir.
ainsi le lapin précédent est capable de connaitre sa couleur car la position du lapin suivant lui donne l'information, seulement le dernier ne connaitra pas sa couleur...
le supreme faciste ne peut donc pas gagner. peut importe l'algorithme choisis pour distribuer les chapeaux..
C'est une forme de communication donc les lapins meurent tous je pense :/
Je crois que que si p = np alors les lapins sont gagnants. Me trompé-je?
Morte de rire, la "Fortranpocalypse" :D Cela dit le Fortran est encore utilisé aujourd'hui dans le domaine du calcul parallèle hautes performances (et pas seulement dans le cadre de la maintenance de vieux programmes). J'ai bossé dans une équipe qui l'utilisais, et encore l'autre jour j'ai un ami qui m'a exhibé fièrement son exemplaire de "Modern Fortran" :D Je me dis que ça ne doit pas être un si mauvais langage du coup.
On prend l'ensemble des algorithmes de taille
Si les lapins se trompent une fois sur deux, ils auront une infinité de bonnes réponses, ce n'est pas suffisant pour empêcher d'avoir une infinité de mauvaises réponses. Il leur faut un moyen de ne plus se tromper après un certain nombre d'essais.
Je vais quand même défendre le Fortran: dans ses dernières versions (90 et +) c'est un langage qui a un très bon ratio performance * fonctionnalité/complexité syntaxique. Allez faire du calcul massivement parallèle sur supercalateur avec du python !!! Maintenant on peut faire de l'orienté objet largement suffisant pour le calcul scientifique. Comparé à du C c'est syntaxiquement beaucoup plus lisible et plus simple (après c'est une question de goût). Bref, si tant de gens dans le domaine du calcul scientifique l'utilise c'est qu'il y a de bonnes raisons !
Je prédis que tu vas prédire que je vais predire que tu vas prédire que je vais choisir cette algorithme. Hmm je sens que je vais trop loin, ou peut-être bien que non ?
Très bel épisode! À la fin tu aurais pu discuter un peu plus de «qui gagne» entre le SF ou les lapins, point très obscur dans les commentaires.
Les lapins ne peuvent choisir d'algorithme leur garantissant la victoire pour la raison invoquée dans l'épisode: tout simplement car si le SF connaît cet algorithme utilisé par les lapins, il peut utiliser l'algo qui renvoie toujours la couleur opposée pour choisir les couleurs.
Mais le même raisonnement montre que le SF ne peut pas non plus choisir d'algorithme lui garantissant la victoire (si les lapins connaissaient cet algo, ils pourraient répondre toujours juste).
Il s'agit donc d'un problème de théorie des jeux sans stratégie gagnante à coup sûr pour l'un ou l'autre parti.
Moi je dis, les lapins de mettent côte à côte, les premiers lapins font en sorte que les blancs soient d’un côté et les noirs de l’autre. Puis les lapins suivant se glissent entre les lapins au milieu de la bande. Les précédents sauront quel chapeau ils portent quand le suivant se mettra à leur gauche ou droite
Ou alors il y a une stratégie qui assure à tous les coups la victoire pour les lapins : ils refusent de répondre. Il ne feront aucune erreur :)