J’approuve, c’est un très joli livre. On y trouve des mathématiques remarquablement profondes, dont une quantité substantielle est abordable avec un bagage théorique assez restreint, ce qui est toujours de bon goût.
Une découverte d’une importance capitale : PowerPoint est Turing-Complet.
Ce qui veut dire que vous pouvez coder ce que vous voulez avec PowerPoint, on peut même y recoder ZdS ! Avis aux amateurs.
PowerPoint est Turing-Complet.
Ce qui veut dire que vous pouvez coder ce que vous voulez avec PowerPoint
Non, ça veut dire qu’en se donnant une machine à mémoire infinie et un temps infini, PowerPoint est capable d’exécuter n’importe quel algo. C’est différent et nettement mois fort que ce qu’on veut souvent faire croire.
Non, ça veut dire qu’en se donnant une machine à mémoire infinie et un temps infini, PowerPoint est capable d’exécuter n’importe quel algo. C’est différent et nettement mois fort que ce qu’on veut souvent faire croire.
Honnêtement je trouve que c’est du chipotage. Personne ne s’est jamais dit que tel ou tel langage était pas cool parce que en vrai si tu n’as pas de mémoire infinie tu ne peux pas exécuter ton algo de la mort qui tue.
D’autant que, pour un algo qui s’exécute en un temps fini (et même pour les algos infinis utilisés en pratique), tu peux toujours trouver une machine à mémoire finie qui peut l’exécuter.
Dans le cas de ZdS, il faudra certainement un gros automate, mais Holosmos sera content, vu que le papier a semble-t-il été écrit via PowerPoint et donc que le support/émulation de Latex semble techniquement faisable. Si ça se trouve on pourra même facilement régler les problèmes de marge verticale sur une formule écrite entre $$ dans un paragraphe.
Personne ne s’est jamais dit que tel ou tel langage était pas cool parce que en vrai si tu n’as pas de mémoire infinie tu ne peux pas exécuter ton algo de la mort qui tue.
Oh, même sans parler de gens qui se plaignent qu’un langage est pas cool parce qu’il a besoin d’une infinité de mémoire (cela dit, perso, un langage qui a besoin d’une infinité de mémoire, je sais pas toi, mais moi je me plains) ; des gens qui se sont dit qu’un langage n’était pas cool parce qu’ils n’avaient pas assez de mémoire pour faire tourner leur algo très simple, il y en a tous les jours. C’est accessoirement pour ça qu’on fait pas tourner un code en Python sur un micro-contrôleur avec 8ko de RAM, et c’est accessoirement pour ça que le fait qu’un langage soit Turing complet n’a rien à voir avec le fait que l’on puisse coder ce qu’on veut avec.
Ce que tu appelles chipotage, c’est quand même la différence entre "ce langage permet d’implementer cet algo" et "ce langage me garantit de pouvoir l’exécuter sur la machine cible". C’est un peu comme si tu disais "un escargot peut se déplacer sur le socle continental, ça veut dire qu’il peut aller du Maroc à l’Afrique du Sud", puis qu’un type te réponde "attention, ça veut juste dire qu’un escargot increvable peut le faire" puis que tu lui répondes "tu chipotes, personne s’est jamais plaint d’un escargot qui mettrait une infinité de temps à faire le tour de la Terre".
C’est le même niveau d’absurdité de conversation, sauf que les gens ne s’en rendent même pas compte à cause du battage fait autour de la notion de Turing-complétude. Et c’est exactement pour ça qu’il est à mes yeux important de se rappeler que la notion de Turing-complétude n’a rien à voir avec une quelconque faisabilité.
Ce que tu appelles chipotage, c’est quand même la différence entre "ce langage permet d’implementer cet algo" et "ce langage me garantit de pouvoir l’exécuter sur la machine cible".
Exactement. Comme je n’ai jamais parlé de machine cible, venir rajouter la contrainte de mémoire infinie est du chipotage à mon sens, vu que tu apportes une objection à un point qui ne fait même pas partie de mon message.
Enfin bon, l’absurdité de ma conversation ne va pas bouleverser ma vie, donc personnellement j’en resterai là.
PowerPoint est Turing-Complet.
Ce qui veut dire que vous pouvez coder ce que vous voulez avec PowerPoint
Non, ça veut dire qu’en se donnant une machine à mémoire infinie et un temps infini, PowerPoint est capable d’exécuter n’importe quel algo. C’est différent et nettement mois fort que ce qu’on veut souvent faire croire.
En plus d’être hors-sujet vis-à-vis du du message de @melepe, ce que tu dis est faux. Là où tu te trompes, c’est sur un point subtile qui est que la notion de Turing-complétude ne se fait pas sur des algorithmes mais sur des fonctions. Par exemple, tu pourrais imaginer un langage Turing-complet dans lequel il n’est pas possible d’écrire le quicksort (même si je n’en connais pas). Mais on m’avait parlé d’un résultat, où il était montré qu’on ne pouvait pas écrire un lambda terme pour décider du min entre deux entiers $n$ et $m$ en $O(min(n,m))$.
Enfin, je pense que la remarque de @melepe portait purement sur une notion de calculabilité. Or, en calculabilité, on s’en fiche de savoir si réimplementé zds, ça va prendre 1 millard de caractères, et simuler le chargement d’une page prendra 10 ans, tout ce qu’on cherche à savoir c’est si faisable, ce qui est exactement ce que nous donne la notion de Turing-complètude. En ça, le texte que je viens de citer est d’autant plus faux quand tu dis non. Car, oui, tu peux imaginer par le biais d’encodage, recoder zds en Powerpoint. Est-ce intéressant pour autant, bien sûr que non…
En plus d’être hors-sujet vis-à-vis du du message de @melepe, ce que tu dis est faux. Là où tu te trompes, c’est sur un point subtile qui est que la notion de Turing-complétude ne se fait pas sur des algorithmes mais sur des fonctions. Par exemple, tu pourrais imaginer un langage Turing-complet dans lequel il n’est pas possible d’écrire le quicksort (même si je n’en connais pas).
Si tu sais faire ça, tu as démontré que la thèse de Church-Turing est fausse (et pour le coup, l’accepter implicitement, c’est quand même super courant…). Ironiquement, si tu ne l’acceptes pas, ça va dans le sens de dire qu’être Turing complet ne permet pas de pouvoir implémenter ce que tu veux…
Enfin, je pense que la remarque de @melepe portait purement sur une notion de calculabilité.
Oui, moi aussi, et c’est bien pour ça que j’ai cru bon de rappeler que "pouvoir coder ce qu’on veut" n’a pas le sens auquel on peut être tenté de penser et n’est que théorique. Je m’attendais pas à une si mauvaise réception de cette tentative de la part du café des sciences. Je m’abstiendrais à l’avenir…
En plus d’être hors-sujet vis-à-vis du du message de @melepe, ce que tu dis est faux. Là où tu te trompes, c’est sur un point subtile qui est que la notion de Turing-complétude ne se fait pas sur des algorithmes mais sur des fonctions. Par exemple, tu pourrais imaginer un langage Turing-complet dans lequel il n’est pas possible d’écrire le quicksort (même si je n’en connais pas).
Si tu sais faire ça, tu as démontré que la thèse de Church-Turing est fausse (et pour le coup, l’accepter implicitement, c’est quand même super courant…). Ironiquement, si tu ne l’acceptes pas, ça va dans le sens de dire qu’être Turing complet ne permet pas de pouvoir implémenter ce que tu veux…
La thèse de Church-Turing parle de fonctions calculables, pas d’algorithmes… donc mon propos est cohérent avec cette thèse. De plus, le résultat dont je te parle a été publié, juste je n’arrive pas a remettre la main sur l’article.
Enfin, je pense que la remarque de @melepe portait purement sur une notion de calculabilité.
Oui, moi aussi, et c’est bien pour ça que j’ai cru bon de rappeler que "pouvoir coder ce qu’on veut" n’a pas le sens auquel on peut être tenté de penser et n’est que théorique. Je m’attendais pas à une si mauvaise réception de cette tentative de la part du café des sciences. Je m’abstiendrais à l’avenir…
@melepe dit quelque chose vrai, et tu commences ton message par non, ce que je trouve étrange pour un rappel. Le soucis que je voulais souligner est justement que tu as repondu a @melepe par un argument de faisabilite, là où ce dernier parle de calculabilite. Or dans votre échange, la distinction n’est pas clair.
Je ne souhaite pas paraître méchant et si c’est le cas je m’en excuse, mais je souhaitais clarifier un propos qui me semblait peu clair.
La thèse de Church-Turing parle de fonctions calculables, pas d’algorithmes…
J’ai vérifié, et tu as raison sur la partie "implémentation d’un algo". La thèse de Church-Turing dit que le fait qu’une fonction soit calculable par une machine de Turing est équivalent au fait qu’elle soit calculable en suivant un algorithme (donc ça parle d’algorithme quand même, je suis pas fou). Si cette thèse s’avère exacte, ça signifie qu’un langage Turing-complete permet d’obtenir le même résultat que n’importe quel algo, mais l’implémentation peut être différente.
Du coup, il faut remplacer "exécuter n’importe quel algo" par "exécuter un truc équivalent à n’importe quel algo" dans mon message plus haut. Ce qui au passage n’en change pas le message de fond, mais au contraire le renforce puisque le sens de "coder ce qu’on veut" en est encore appauvri, et même plus seulement du point de vue de la faisabilité…
c’est quand même la différence entre "ce langage permet d’implementer cet algo" et "ce langage me garantit de pouvoir l’exécuter sur la machine cible".
C’est encore plus fort que ça, puisque ça devrait plutôt être la différence entre "pouvoir obtenir le même résultat que cet algo" et "pouvoir implémenter et exécuter cet algo".
La thèse de Church-Turing parle de fonctions calculables, pas d’algorithmes…
J’ai vérifié, et tu as raison sur la partie "implémentation d’un algo". La thèse de Church-Turing dit que le fait qu’une fonction soit calculable par une machine de Turing est équivalent au fait qu’elle soit calculable en suivant un algorithme (donc ça parle d’algorithme quand même, je suis pas fou). Si cette thèse s’avère exacte, ça signifie qu’un langage Turing-complete permet d’obtenir le même résultat que n’importe quel algo, mais l’implémentation peut être différente.
Du coup, il faut remplacer "exécuter n’importe quel algo" par "exécuter un truc équivalent à n’importe quel algo" dans mon message plus haut. Ce qui au passage n’en change pas le message de fond, mais au contraire le renforce puisque le sens de "coder ce qu’on veut" en est encore appauvri, et même plus seulement du point de vue de la faisabilité…
En fait, je ne comprends juste pas le message que tu souhaites faire passer. Même la notion de faisabilité n’est pas clair. Est-ce que tu souhaites dire faisable en pratique ? ou faisable théoriquement ?
Pour la première hypothèse, on s’en fiche car ce n’est pas du tout la notion véhiculé par cette thèse. Pour la seconde, dans ce cas là, cela revient à la notion de calculabilité et dans ce cas là je comprends pas du tout ce que tu souhaites dire.
c’est quand même la différence entre "ce langage permet d’implementer cet algo" et "ce langage me garantit de pouvoir l’exécuter sur la machine cible".
Qu’entends-tu par "garantir" ? Là encore je suis largué par ton message, car modulo des encodages, tu peux faire ce que tu veux tant que tu vis avec des formalismes Turing-complets.
C’est encore plus fort que ça, puisque ça devrait plutôt être la différence entre "pouvoir obtenir le même résultat que cet algo" et "pouvoir implémenter et exécuter cet algo".
Modulo des encodages, tu peux faire ce que tu veux, notamment à partir du moment où tu as la notion de machine de Turing universelle. Du coup, je te suis encore moins…
Mon message, c’est juste qu’il faut avoir conscience que le fait qu’un langage est Turing-complet ne donne qu’une information sur ce qu’il est possible de calculer avec. Chose que ne véhicule pas la phrase "on peut coder ce qu’on veut avec", écrite beaucoup trop souvent sans être contextualisée, et résultant en une excitation excessive autour du concept. Déjà parce que le verbe "pouvoir" a un sens ambiguë (on a la possibilité théorique d’implémenter le calcul, pas forcément la possibilité pratique de le faire ni d’exécuter le programme résultant), ensuite parce que "ce que veut" est trompeur (on peut implémenter le calcul, mais pas forcément l’algo, et ça, c’est toi qui m’en as fait prendre conscience).
Mais on m’avait parlé d’un résultat, où il était montré qu’on ne pouvait pas écrire un lambda terme pour décider du min entre deux entiers $n$ et $m$ en $O(min(n,m))$.
Par contre pour le lambda-calcul, en représentant les entiers en binaire c’est possible de faire en $O(\min(\log n,\log m))$. L’article que j’ai donné ne parle que des fonctions primitives récursives justement. Est-ce que c’était autre chose ?
J’aime beaucoup cette façon de faire des vidéo sur un sujet mathématique. Qu’est-ce que vous en pensez ? Est-ce que c’est une bonne manière de concilier formalisme/vulgarisation ?
N’hésitez pas à développer, ça sera utile (vous le saurez bientôt pourquoi).
J’aime beaucoup cette façon de faire des vidéo sur un sujet mathématique. Qu’est-ce que vous en pensez ?
Sincèrement, je sais pas si ce commentaire te sera utile mais les prises de vue de drones me font décrocher parce que j’admire plus l’image que j’écoute et déjà qu’en anglais c’est pas facile alors quand on loupe des bouts c’est encore plus dur.
N’hésitez pas à développer, ça sera utile (vous le saurez bientôt pourquoi).
Je trouve qu’il n’explique pas assez les maths et qu’il passe trop de temps à dire des trucs d’interprétation (les personnes qui débattent mais qui n’échangeront jamais rien, ou la citation de Mandela, puis son « raisonnement » de si on internalise quelque chose on va continuer à faire la même chose, etc. je vois pas assez bien le lien avec les maths et je ne comprends pas assez précisément ce qu’il veut dire pour vraiment juger).
Ensuite je trouve que les justifications ne sont pas assez détaillées. Par exemple, pour le truc des deux laboratoires, il faut que les résultats des labos soient indépendants et indépendants sachant $H$ pour pouvoir appliquer ce qui est dit. C’est pas super intuitif le lien entre (indépendance sachant $H$ et indépendance sachant non $H$) et indépendance tout court. C’est sûrement un détail pas trop important pour le propos global mais ça m’a dérangé par exemple (j’aurais bien aimé avoir un cadre plus clair).
Mais on m’avait parlé d’un résultat, où il était montré qu’on ne pouvait pas écrire un lambda terme pour décider du min entre deux entiers $n$ et $m$ en $O(min(n,m))$.
Par contre pour le lambda-calcul, en représentant les entiers en binaire c’est possible de faire en $O(\min(\log n,\log m))$. L’article que j’ai donné ne parle que des fonctions primitives récursives justement. Est-ce que c’était autre chose ?
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
!