{"id":9922,"date":"2025-10-31T17:02:00","date_gmt":"2025-10-31T16:02:00","guid":{"rendered":"https:\/\/scienceetonnante.com\/blog\/?p=9922"},"modified":"2025-11-04T17:57:45","modified_gmt":"2025-11-04T16:57:45","slug":"les-machines-de-turing","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2025\/10\/31\/les-machines-de-turing\/","title":{"rendered":"Les machines de Turing"},"content":{"rendered":"\n<p>La vid\u00e9o du jour parle des travaux de Turing qui pr\u00e9figurent l&rsquo;ordinateur moderne !<br><\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe title=\"Les Machines de Turing\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/o_swEgbBhMU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" class=\"lazyload\" data-load-mode=\"1\"><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Quelques pistes de compl\u00e9ments en vrac pour celles et ceux qui voudraient aller plus loin :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>J&rsquo;ai fait le choix de ne pas pr\u00e9senter le sujet en parlant du <strong>probl\u00e8me de la d\u00e9cision<\/strong> de Hilbert et Ackermann (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Entscheidungsproblem\" target=\"_blank\" rel=\"noopener\">Entscheidungsproblem<\/a>). J&rsquo;avoue que j&rsquo;ai h\u00e9sit\u00e9 et que la premi\u00e8re version du script suivait ce chemin plut\u00f4t historique. Et j&rsquo;ai finalement d\u00e9cid\u00e9 de choisir une route plus simple. <\/li>\n\n\n\n<li>J&rsquo;ai aussi largement esquiv\u00e9 le <a href=\"https:\/\/en.wikipedia.org\/wiki\/Lambda_calculus\" target=\"_blank\" rel=\"noopener\">lambda-calcul<\/a>&#8230;peut-\u00eatre une prochaine fois !<\/li>\n\n\n\n<li>Je me suis rendu compte en montant la vid\u00e9o que malheureusement <strong>le mot \u00ab\u00a0th\u00e8se\u00a0\u00bb avait ici deux sens<\/strong>. Je dis que Turing \u00e9tait l&rsquo;\u00e9tudiant en th\u00e8se de Church (donc th\u00e8se est \u00e0 entendre dans son sens \u00ab\u00a0dipl\u00f4me universitaire\u00a0\u00bb) et ensuite je parle de la \u00ab\u00a0th\u00e8se\u00a0\u00bb du Church-Turing, qui l\u00e0 fait r\u00e9f\u00e9rence \u00e0 une proposition consid\u00e9r\u00e9e comme vraie.<\/li>\n\n\n\n<li>Sur l&rsquo;affirmation habituelle que l&rsquo;ENIAC est le premier ordinateur programmable, en fait il semblerait que le <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Zuse_3\" target=\"_blank\" rel=\"noopener\">Zuse 3<\/a> construit \u00e0 Berlin en 1941 puisse pr\u00e9tendre \u00e0 cet honneur. Si l&rsquo;ENIAC est bien le premier ordinateur \u00e9lectronique qui soit Turing-complet, <strong>le Zuse 3 \u00e9tait d\u00e9j\u00e0 Turing-complet<\/strong> mais en utilisant des commutateurs \u00e9lectro-m\u00e9caniques.<\/li>\n\n\n\n<li>Pour pr\u00e9senter le fait que toutes les fonctions ne sont pas a priori calculables, j&rsquo;ai utilis\u00e9 le nombre de solutions de l&rsquo;\u00e9quation $x^2=y^3+n$. Il s&rsquo;agit d&rsquo;<strong>une \u00e9quation dite de <a href=\"https:\/\/en.wikipedia.org\/wiki\/Mordell_curve\" target=\"_blank\" rel=\"noopener\">Mordell<\/a><\/strong><a href=\"https:\/\/en.wikipedia.org\/wiki\/Mordell_curve\" target=\"_blank\" rel=\"noopener\">.<\/a> A priori on pourrait se dire qu&rsquo;elle pourrait avoir une infinit\u00e9 de solutions, mais \u00e7a n&rsquo;est pas le cas ! Mordell a d\u00e9montr\u00e9 qu&rsquo;elle n&rsquo;avait qu&rsquo;un nombre fini de solutions enti\u00e8res (\u00e0 moins que \u00e7a ne d\u00e9coule du <a href=\"https:\/\/en.wikipedia.org\/wiki\/Siegel%27s_theorem_on_integral_points\" target=\"_blank\" rel=\"noopener\">th\u00e9or\u00e8me de Siegel<\/a>&#8230;j&rsquo;ai un peu de mal \u00e0 comprendre la chronologie du domaine !)<\/li>\n\n\n\n<li>Sur les fonctions exotiques, il faudra que je parle un jour du <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Castor_affair\u00e9\" target=\"_blank\" rel=\"noopener\"><strong>castor affair\u00e9<\/strong><\/a> !<\/li>\n\n\n\n<li>Sur <strong>le caract\u00e8re Turing-complet de LaTeX<\/strong>, j&rsquo;ai essay\u00e9 vite-fait de faire un truc du genre lui faire calculer les d\u00e9cimales de pi (\u00e7a doit \u00eatre jouable avec des compteurs) mais j&rsquo;ai finalement renonc\u00e9 !<\/li>\n\n\n\n<li>Et pour finir une interrogation : <strong>les cerveaux humains sont ils des machines de Turing ?<\/strong><\/li>\n<\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>La vid\u00e9o du jour parle des travaux de Turing qui pr\u00e9figurent l&rsquo;ordinateur moderne ! Quelques pistes de compl\u00e9ments en vrac pour celles et ceux qui voudraient aller plus loin :<\/p>\n","protected":false},"author":1,"featured_media":9923,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[100],"class_list":{"0":"post-9922","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-informatique","8":"category-mathematiques","9":"tag-informatique-theorique"},"jetpack_featured_media_url":"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2025\/10\/transition.png","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9922","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=9922"}],"version-history":[{"count":5,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9922\/revisions"}],"predecessor-version":[{"id":9929,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9922\/revisions\/9929"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media\/9923"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=9922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=9922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=9922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}