En\u00a0informatique th\u00e9orique, une\u00a0machine de Turing\u00a0est un mod\u00e8le abstrait du fonctionnement des\u00a0appareils m\u00e9caniques de calcul, tel un\u00a0ordinateur. Ce mod\u00e8le a \u00e9t\u00e9 imagin\u00e9 par\u00a0Alan Turing\u00a0en 1936, en vue de donner une d\u00e9finition pr\u00e9cise au concept d\u2019algorithme\u00a0ou de \u00ab\u00a0proc\u00e9dure m\u00e9canique\u00a0\u00bb. Il est toujours largement utilis\u00e9 en\u00a0informatique th\u00e9orique, en particulier dans les domaines de la\u00a0complexit\u00e9 algorithmique\u00a0et de la\u00a0calculabilit\u00e9.<\/p>\n\n\n\n
\u00c0 l’origine, le concept de machine de Turing, invent\u00e9 avant l’ordinateur, \u00e9tait cens\u00e9 repr\u00e9senter une personne virtuelle ex\u00e9cutant une proc\u00e9dure bien d\u00e9finie, en changeant le contenu des cases d’un ruban infini, en choisissant ce contenu parmi un ensemble fini de\u00a0symboles. D’autre part, \u00e0 chaque \u00e9tape de la proc\u00e9dure, la personne doit se placer dans un \u00e9tat particulier parmi un ensemble fini d’\u00e9tats. La proc\u00e9dure est formul\u00e9e en termes d’\u00e9tapes \u00e9l\u00e9mentaires du type\u00a0: \u00ab\u00a0si vous \u00eates dans\u00a0l’\u00e9tat 42\u00a0et que le symbole contenu sur la case que vous regardez est \u00ab\u00a00\u00a0\u00bb, alors remplacer ce symbole par un \u00ab\u00a01\u00a0\u00bb, passer dans\u00a0l’\u00e9tat 17, et regarder maintenant la case adjacente \u00e0 droite\u00a0\u00bb.<\/p>\n\n\n\n
Une machine de Turing est un objet de pens\u00e9e\u00a0: son ruban est infini, et donc la m\u00e9moire d’une machine de Turing est infinie. Une machine de Turing n’engendre jamais de\u00a0d\u00e9bordement de m\u00e9moire, contrairement \u00e0 un ordinateur dont la m\u00e9moire est finie. En oubliant ce probl\u00e8me de m\u00e9moire, on peut\u00a0simuler\u00a0une machine de Turing sur un ordinateur moderne.<\/a><\/a>La machine de Turing en Lego cr\u00e9\u00e9e \u00e0 l\u2019occasion de l\u2019ann\u00e9e Turing par Elie Gedeon, Etienne Py-Circan, Anael Grandjean, Florent Robic, Robin Perrotin, Thomas Lambert, Yannick L\u00e9o, Kevin Perrot et Eddy Caron.<\/p>\n\n\n\n Il est aussi possible de construire des machines de Turing purement m\u00e9caniques. La machine de Turing, objet de pens\u00e9e, a pu ainsi \u00eatre\u00a0r\u00e9ifi\u00e9e\u00a0\u00e0 de nombreuses reprises en utilisant des techniques parfois assez originales.<\/p>\n","protected":false},"excerpt":{"rendered":" En\u00a0informatique th\u00e9orique, une\u00a0machine de Turing\u00a0est un mod\u00e8le abstrait du fonctionnement des\u00a0appareils m\u00e9caniques de calcul, tel un\u00a0ordinateur. Ce mod\u00e8le a \u00e9t\u00e9 imagin\u00e9 par\u00a0Alan Turing\u00a0en 1936, en vue de donner une d\u00e9finition pr\u00e9cise au concept d\u2019algorithme\u00a0ou de \u00ab\u00a0proc\u00e9dure m\u00e9canique\u00a0\u00bb. Il est toujours largement utilis\u00e9 en\u00a0informatique th\u00e9orique, en particulier dans les domaines de la\u00a0complexit\u00e9 algorithmique\u00a0et de la\u00a0calculabilit\u00e9. \u00c0 […]<\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/comments?post=192"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192\/revisions"}],"predecessor-version":[{"id":193,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192\/revisions\/193"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/media?parent=192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/categories?post=192"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/tags?post=192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![<\/a>](\"https:\/\/commons.wikimedia.org\/wiki\/File:Lego_Turing_Machine.jpg?uselang=fr\"){kind=link}
![<\/a>La machine de Turing en Lego cr\u00e9\u00e9e \u00e0 l\u2019occasion de l\u2019ann\u00e9e Turing par Elie Gedeon, Etienne Py-Circan, Anael Grandjean, Florent Robic, Robin Perrotin, Thomas Lambert, Yannick L\u00e9o, Kevin Perrot et Eddy Caron.<\/p>\n\n\n\nIl est aussi possible de construire des machines de Turing purement m\u00e9caniques. La machine de Turing, objet de pens\u00e9e, a pu ainsi \u00eatre\u00a0r\u00e9ifi\u00e9e\u00a0\u00e0 de nombreuses reprises en utilisant des techniques parfois assez originales.<\/p>\n","protected":false},"excerpt":{"rendered":"En\u00a0informatique th\u00e9orique, une\u00a0machine de Turing\u00a0est un mod\u00e8le abstrait du fonctionnement des\u00a0appareils m\u00e9caniques de calcul, tel un\u00a0ordinateur. Ce mod\u00e8le a \u00e9t\u00e9 imagin\u00e9 par\u00a0Alan Turing\u00a0en 1936, en vue de donner une d\u00e9finition pr\u00e9cise au concept d\u2019algorithme\u00a0ou de \u00ab\u00a0proc\u00e9dure m\u00e9canique\u00a0\u00bb. Il est toujours largement utilis\u00e9 en\u00a0informatique th\u00e9orique, en particulier dans les domaines de la\u00a0complexit\u00e9 algorithmique\u00a0et de la\u00a0calculabilit\u00e9. \u00c0 […]<\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[],"_links":{"self":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192"}],"collection":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/comments?post=192"}],"version-history":[{"count":1,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192\/revisions"}],"predecessor-version":[{"id":193,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/posts\/192\/revisions\/193"}],"wp:attachment":[{"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/media?parent=192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/categories?post=192"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/yb-isn.fr\/2021\/nsi\/matthieu\/wp-json\/wp\/v2\/tags?post=192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}](\"https:\/\/fr.wikipedia.org\/wiki\/Fichier:Lego_Turing_Machine.jpg\"){kind=link}