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 ?
