La vidéo du jour parle des travaux de Turing qui préfigurent l’ordinateur moderne !
Quelques pistes de compléments en vrac pour celles et ceux qui voudraient aller plus loin :
- J’ai fait le choix de ne pas présenter le sujet en parlant du problème de la décision de Hilbert et Ackermann (Entscheidungsproblem). J’avoue que j’ai hésité et que la première version du script suivait ce chemin plutôt historique. Et j’ai finalement décidé de choisir une route plus simple.
- J’ai aussi largement esquivé le lambda-calcul…peut-être une prochaine fois !
- Je me suis rendu compte en montant la vidéo que malheureusement le mot « thèse » avait ici deux sens. Je dis que Turing était l’étudiant en thèse de Church (donc thèse est à entendre dans son sens « diplôme universitaire ») et ensuite je parle de la « thèse » du Church-Turing, qui là fait référence à une proposition considérée comme vraie.
- Sur l’affirmation habituelle que l’ENIAC est le premier ordinateur programmable, en fait il semblerait que le Zuse 3 construit à Berlin en 1941 puisse prétendre à cet honneur. Si l’ENIAC est bien le premier ordinateur électronique qui soit Turing-complet, le Zuse 3 était déjà Turing-complet mais en utilisant des commutateurs électro-mécaniques.
- Pour présenter le fait que toutes les fonctions ne sont pas a priori calculables, j’ai utilisé le nombre de solutions de l’équation $x^2=y^3+n$. Il s’agit d’une équation dite de Mordell. A priori on pourrait se dire qu’elle pourrait avoir une infinité de solutions, mais ça n’est pas le cas ! Mordell a démontré qu’elle n’avait qu’un nombre fini de solutions entières (à moins que ça ne découle du théorème de Siegel…j’ai un peu de mal à comprendre la chronologie du domaine !)
- Sur les fonctions exotiques, il faudra que je parle un jour du castor affairé !
- Sur le caractère Turing-complet de LaTeX, j’ai essayé vite-fait de faire un truc du genre lui faire calculer les décimales de pi (ça doit être jouable avec des compteurs) mais j’ai finalement renoncé !
- Et pour finir une interrogation : les cerveaux humains sont ils des machines de Turing ?
1 Comment
Excellente vidéo, très pédagogique, comme souvent 🙂
« Et pour finir une interrogation : les cerveaux humains sont ils des machines de Turing ? »
Je dirais probablement oui: si on pense que la physique est simulable (thèse de Church-Turing-Deutsch), alors un cerveau humain peut être aussi complexe qu’on veut, ça reste un objet physique qui est donc simulable (potentiellement en complexité haute en mémoire ou temps) par une machine de Turing universelle.
(au passage, j’ai l’impression que tu utilises « thèse de Church-Turing » dans la vidéo mais que tu expliques plutôt celle de « thèse de Church-Turing-Deutsch », ie la thèse que la physique du monde réel peut être simulée par une machine de Turing universelle)
On peut bien sûr rejeter la thèse de Church-Turing-Deutsch, auquel cas ce n’est pas un cerveau humain qui est spécifiquement non-simulable mais simplement « la Nature » (certains de ses processus)
Ou on peut bien sûr penser qu’il y a quelque de non-physique impliqué dans le cerveau (ou la conscience humaine, pour le prendre au sens large et ne pas être pédant sur la question du « cerveau » qui peut être défini comme l’objet physique et donc simulable si la Nature l’est), mais il me semble que rien ne l’indique: serait-le cas pour le cerveau/la conscience d’un chat? Quid d’une souris? D’un poisson rouge? D’une araignée?
On est arrivé à un point de connaissance scientifique où on se rend quasiment compte comment la complexité qu’on observe peut émerger de lois mathématiques simples, et je pense (crains) qu’on en ait de plus en plus la preuve empirique avec les IA qui reproduisent de mieux en mieux les fonctions du cerveau humain.
Tout ça modulo le problème difficile de la conscience bien sûr, mais je n’irais pas jusqu’à y mettre la limite à Church-Turing-Deutsch