CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="fr" dir="ltr"> <head> <meta charset="UTF-8"> <title>Machine de Turing — Wikipédia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )frwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"dmy","wgMonthNames":["","janvier","février","mars","avril","mai","juin","juillet","août","septembre","octobre","novembre","décembre"],"wgRequestId":"d6c87abb-5273-4e92-9de6-2fe4c0c3ae64","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Machine_de_Turing","wgTitle":"Machine de Turing","wgCurRevisionId":219498690,"wgRevisionId":219498690,"wgArticleId":54894,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article contenant un appel à traduction en anglais","Catégorie Commons avec lien local identique sur Wikidata","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Logique mathématique","Calculabilité","Théorie de la complexité des algorithmes","Théorie des automates","Alan Turing","Modèles de calcul"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr", "wgPageContentModel":"wikitext","wgRelevantPageName":"Machine_de_Turing","wgRelevantArticleId":54894,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Machines_de_Turing","wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fr","pageLanguageDir":"ltr","pageVariantFallbacks":"fr"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgInternalRedirectTargetUrl":"/wiki/Machine_de_Turing","wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q163310","wgCheckUserClientHintsHeadersJsApi":[ "brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","mediawiki.page.gallery.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js", "ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.gadget.Wdsearch","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cmediawiki.page.gallery.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/1200px-Hi%C3%A9rarchie_d%27automates.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="900"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/800px-Hi%C3%A9rarchie_d%27automates.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="600"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/640px-Hi%C3%A9rarchie_d%27automates.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="480"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Machine de Turing — Wikipédia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fr.m.wikipedia.org/wiki/Machine_de_Turing"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Machine_de_Turing&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipédia (fr)"> <link rel="EditURI" type="application/rsd+xml" href="//fr.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fr.wikipedia.org/wiki/Machine_de_Turing"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr"> <link rel="alternate" type="application/atom+xml" title="Flux Atom de Wikipédia" href="/w/index.php?title=Sp%C3%A9cial:Modifications_r%C3%A9centes&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Machine_de_Turing rootpage-Machine_de_Turing skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Aller au contenu</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principal" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principal</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">masquer</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_principal" title="Accueil général [z]" accesskey="z"><span>Accueil</span></a></li><li id="n-thema" class="mw-list-item"><a href="/wiki/Portail:Accueil"><span>Portails thématiques</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Page_au_hasard" title="Affiche un article au hasard [x]" accesskey="x"><span>Article au hasard</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Contact"><span>Contact</span></a></li> </ul> </div> </div> <div id="p-Contribuer" class="vector-menu mw-portlet mw-portlet-Contribuer" > <div class="vector-menu-heading"> Contribuer </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-aboutwp" class="mw-list-item"><a href="/wiki/Aide:D%C3%A9buter"><span>Débuter sur Wikipédia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aide:Accueil" title="Accès à l’aide"><span>Aide</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_de_la_communaut%C3%A9" title="À propos du projet, ce que vous pouvez faire, où trouver les informations"><span>Communauté</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Modifications_r%C3%A9centes" title="Liste des modifications récentes sur le wiki [r]" accesskey="r"><span>Modifications récentes</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikip%C3%A9dia:Accueil_principal" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipédia" src="/static/images/mobile/copyright/wikipedia-wordmark-fr.svg" style="width: 7.4375em; height: 1.125em;"> <img class="mw-logo-tagline" alt="l'encyclopédie libre" src="/static/images/mobile/copyright/wikipedia-tagline-fr.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Sp%C3%A9cial:Recherche" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Rechercher sur Wikipédia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia" aria-label="Rechercher sur Wikipédia" autocapitalize="sentences" title="Rechercher sur Wikipédia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Outils personnels"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifier l'apparence de la taille, de la largeur et de la couleur de la police de la page" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Apparence" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Apparence</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_fr.wikipedia.org&uselang=fr" class=""><span>Faire un don</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Machine+de+Turing" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire." class=""><span>Créer un compte</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Machine+de+Turing" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o" class=""><span>Se connecter</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Plus d’options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Outils personnels" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Outils personnels</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utilisateur" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_fr.wikipedia.org&uselang=fr"><span>Faire un don</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Machine+de+Turing" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Créer un compte</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Machine+de+Turing" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Se connecter</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages pour les contributeurs déconnectés <a href="/wiki/Aide:Premiers_pas" aria-label="En savoir plus sur la contribution"><span>en savoir plus</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_contributions" title="Une liste des modifications effectuées depuis cette adresse IP [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_discussions" title="La page de discussion pour les contributions depuis cette adresse IP [n]" accesskey="n"><span>Discussion</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Sommaire" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Sommaire</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">masquer</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Début</div> </a> </li> <li id="toc-Définition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Définition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Définition</span> </div> </a> <ul id="toc-Définition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Définition_formelle" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Définition_formelle"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Définition formelle</span> </div> </a> <ul id="toc-Définition_formelle-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Exemples" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Exemples"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Exemples</span> </div> </a> <button aria-controls="toc-Exemples-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Exemples</span> </button> <ul id="toc-Exemples-sublist" class="vector-toc-list"> <li id="toc-Doubler_le_nombre_de_‘1’" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Doubler_le_nombre_de_‘1’"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Doubler le nombre de ‘1’</span> </div> </a> <ul id="toc-Doubler_le_nombre_de_‘1’-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Calculer_un_tiers_en_binaire" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Calculer_un_tiers_en_binaire"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Calculer un tiers en binaire</span> </div> </a> <ul id="toc-Calculer_un_tiers_en_binaire-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Machines_de_Turing_universelles" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Machines_de_Turing_universelles"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Machines de Turing universelles</span> </div> </a> <ul id="toc-Machines_de_Turing_universelles-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Réalisation_d'une_machine_de_Turing" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Réalisation_d'une_machine_de_Turing"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Réalisation d'une machine de Turing</span> </div> </a> <ul id="toc-Réalisation_d'une_machine_de_Turing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Références_et_bibliographie" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Références_et_bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Références et bibliographie</span> </div> </a> <button aria-controls="toc-Références_et_bibliographie-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Références et bibliographie</span> </button> <ul id="toc-Références_et_bibliographie-sublist" class="vector-toc-list"> <li id="toc-Références" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Références"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Références</span> </div> </a> <ul id="toc-Références-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliographie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Bibliographie</span> </div> </a> <ul id="toc-Bibliographie-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Voir_aussi" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voir_aussi"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Voir aussi</span> </div> </a> <button aria-controls="toc-Voir_aussi-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Voir aussi</span> </button> <ul id="toc-Voir_aussi-sublist" class="vector-toc-list"> <li id="toc-Articles_connexes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Articles_connexes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Liens_externes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Liens_externes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>Liens externes</span> </div> </a> <ul id="toc-Liens_externes-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Machine de Turing</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Aller à un article dans une autre langue. Disponible en 66 langues." > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-66" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">66 langues</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-als mw-list-item"><a href="https://als.wikipedia.org/wiki/Turingmaschine" title="Turingmaschine – alémanique" lang="gsw" hreflang="gsw" data-title="Turingmaschine" data-language-autonym="Alemannisch" data-language-local-name="alémanique" class="interlanguage-link-target"><span>Alemannisch</span></a></li><li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A2%D9%84%D8%A9_%D8%AA%D9%88%D8%B1%D9%86%D8%BA" title="آلة تورنغ – arabe" lang="ar" hreflang="ar" data-title="آلة تورنغ" data-language-autonym="العربية" data-language-local-name="arabe" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-be mw-list-item"><a href="https://be.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D1%8B%D0%BD%D0%B0_%D0%A6%D1%8C%D1%8E%D1%80%D1%8B%D0%BD%D0%B3%D0%B0" title="Машына Цьюрынга – biélorusse" lang="be" hreflang="be" data-title="Машына Цьюрынга" data-language-autonym="Беларуская" data-language-local-name="biélorusse" class="interlanguage-link-target"><span>Беларуская</span></a></li><li class="interlanguage-link interwiki-be-x-old mw-list-item"><a href="https://be-tarask.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D1%8B%D0%BD%D0%B0_%D0%A2%E2%80%99%D1%8E%D1%80%D1%8B%D0%BD%D0%B3%D0%B0" title="Машына Т’юрынга – Belarusian (Taraškievica orthography)" lang="be-tarask" hreflang="be-tarask" data-title="Машына Т’юрынга" data-language-autonym="Беларуская (тарашкевіца)" data-language-local-name="Belarusian (Taraškievica orthography)" class="interlanguage-link-target"><span>Беларуская (тарашкевіца)</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BD%D0%B0_%D0%A2%D1%8E%D1%80%D0%B8%D0%BD%D0%B3" title="Машина на Тюринг – bulgare" lang="bg" hreflang="bg" data-title="Машина на Тюринг" data-language-autonym="Български" data-language-local-name="bulgare" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Turingova_ma%C5%A1ina" title="Turingova mašina – bosniaque" lang="bs" hreflang="bs" data-title="Turingova mašina" data-language-autonym="Bosanski" data-language-local-name="bosniaque" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/M%C3%A0quina_de_Turing" title="Màquina de Turing – catalan" lang="ca" hreflang="ca" data-title="Màquina de Turing" data-language-autonym="Català" data-language-local-name="catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%D9%85%DB%95%DA%A9%DB%8C%D9%86%DB%95%DB%8C_%D8%AA%DB%8C%D9%88%D8%B1%DB%8C%D9%86%DA%AF" title="مەکینەی تیورینگ – sorani" lang="ckb" hreflang="ckb" data-title="مەکینەی تیورینگ" data-language-autonym="کوردی" data-language-local-name="sorani" class="interlanguage-link-target"><span>کوردی</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Turing%C5%AFv_stroj" title="Turingův stroj – tchèque" lang="cs" hreflang="cs" data-title="Turingův stroj" data-language-autonym="Čeština" data-language-local-name="tchèque" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Turingmaskine" title="Turingmaskine – danois" lang="da" hreflang="da" data-title="Turingmaskine" data-language-autonym="Dansk" data-language-local-name="danois" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Turingmaschine" title="Turingmaschine – allemand" lang="de" hreflang="de" data-title="Turingmaschine" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%9C%CE%B7%CF%87%CE%B1%CE%BD%CE%AE_%CE%A4%CE%BF%CF%8D%CF%81%CE%B9%CE%BD%CE%B3%CE%BA" title="Μηχανή Τούρινγκ – grec" lang="el" hreflang="el" data-title="Μηχανή Τούρινγκ" data-language-autonym="Ελληνικά" data-language-local-name="grec" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Turing_machine" title="Turing machine – anglais" lang="en" hreflang="en" data-title="Turing machine" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Ma%C5%9Dino_de_Turing" title="Maŝino de Turing – espéranto" lang="eo" hreflang="eo" data-title="Maŝino de Turing" data-language-autonym="Esperanto" data-language-local-name="espéranto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing" title="Máquina de Turing – espagnol" lang="es" hreflang="es" data-title="Máquina de Turing" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Turingi_masin" title="Turingi masin – estonien" lang="et" hreflang="et" data-title="Turingi masin" data-language-autonym="Eesti" data-language-local-name="estonien" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Turingen_makina" title="Turingen makina – basque" lang="eu" hreflang="eu" data-title="Turingen makina" data-language-autonym="Euskara" data-language-local-name="basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF" title="ماشین تورینگ – persan" lang="fa" hreflang="fa" data-title="ماشین تورینگ" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Turingin_kone" title="Turingin kone – finnois" lang="fi" hreflang="fi" data-title="Turingin kone" data-language-autonym="Suomi" data-language-local-name="finnois" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-fur mw-list-item"><a href="https://fur.wikipedia.org/wiki/Machine_di_Turing" title="Machine di Turing – frioulan" lang="fur" hreflang="fur" data-title="Machine di Turing" data-language-autonym="Furlan" data-language-local-name="frioulan" class="interlanguage-link-target"><span>Furlan</span></a></li><li class="interlanguage-link interwiki-ga mw-list-item"><a href="https://ga.wikipedia.org/wiki/Meais%C3%ADn_Turing" title="Meaisín Turing – irlandais" lang="ga" hreflang="ga" data-title="Meaisín Turing" data-language-autonym="Gaeilge" data-language-local-name="irlandais" class="interlanguage-link-target"><span>Gaeilge</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/M%C3%A1quina_de_Turing" title="Máquina de Turing – galicien" lang="gl" hreflang="gl" data-title="Máquina de Turing" data-language-autonym="Galego" data-language-local-name="galicien" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9E%D7%9B%D7%95%D7%A0%D7%AA_%D7%98%D7%99%D7%95%D7%A8%D7%99%D7%A0%D7%92" title="מכונת טיורינג – hébreu" lang="he" hreflang="he" data-title="מכונת טיורינג" data-language-autonym="עברית" data-language-local-name="hébreu" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Turingov_stroj" title="Turingov stroj – croate" lang="hr" hreflang="hr" data-title="Turingov stroj" data-language-autonym="Hrvatski" data-language-local-name="croate" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Turing-g%C3%A9p" title="Turing-gép – hongrois" lang="hu" hreflang="hu" data-title="Turing-gép" data-language-autonym="Magyar" data-language-local-name="hongrois" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B9%D5%B5%D5%B8%D6%82%D6%80%D5%AB%D5%B6%D5%A3%D5%AB_%D5%B4%D5%A5%D6%84%D5%A5%D5%B6%D5%A1" title="Թյուրինգի մեքենա – arménien" lang="hy" hreflang="hy" data-title="Թյուրինգի մեքենա" data-language-autonym="Հայերեն" data-language-local-name="arménien" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-ia mw-list-item"><a href="https://ia.wikipedia.org/wiki/Machina_de_Turing" title="Machina de Turing – interlingua" lang="ia" hreflang="ia" data-title="Machina de Turing" data-language-autonym="Interlingua" data-language-local-name="interlingua" class="interlanguage-link-target"><span>Interlingua</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Mesin_Turing" title="Mesin Turing – indonésien" lang="id" hreflang="id" data-title="Mesin Turing" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonésien" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Mashino_di_Turing" title="Mashino di Turing – ido" lang="io" hreflang="io" data-title="Mashino di Turing" data-language-autonym="Ido" data-language-local-name="ido" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Macchina_di_Turing" title="Macchina di Turing – italien" lang="it" hreflang="it" data-title="Macchina di Turing" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3" title="チューリングマシン – japonais" lang="ja" hreflang="ja" data-title="チューリングマシン" data-language-autonym="日本語" data-language-local-name="japonais" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ka mw-list-item"><a href="https://ka.wikipedia.org/wiki/%E1%83%A2%E1%83%A3%E1%83%A0%E1%83%98%E1%83%9C%E1%83%92%E1%83%98%E1%83%A1_%E1%83%9B%E1%83%90%E1%83%9C%E1%83%A5%E1%83%90%E1%83%9C%E1%83%90" title="ტურინგის მანქანა – géorgien" lang="ka" hreflang="ka" data-title="ტურინგის მანქანა" data-language-autonym="ქართული" data-language-local-name="géorgien" class="interlanguage-link-target"><span>ქართული</span></a></li><li class="interlanguage-link interwiki-ki mw-list-item"><a href="https://ki.wikipedia.org/wiki/Macini_ya_Turing" title="Macini ya Turing – kikuyu" lang="ki" hreflang="ki" data-title="Macini ya Turing" data-language-autonym="Gĩkũyũ" data-language-local-name="kikuyu" class="interlanguage-link-target"><span>Gĩkũyũ</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%8A%9C%EB%A7%81_%EA%B8%B0%EA%B3%84" title="튜링 기계 – coréen" lang="ko" hreflang="ko" data-title="튜링 기계" data-language-autonym="한국어" data-language-local-name="coréen" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-la mw-list-item"><a href="https://la.wikipedia.org/wiki/Machina_Turing" title="Machina Turing – latin" lang="la" hreflang="la" data-title="Machina Turing" data-language-autonym="Latina" data-language-local-name="latin" class="interlanguage-link-target"><span>Latina</span></a></li><li class="interlanguage-link interwiki-lb mw-list-item"><a href="https://lb.wikipedia.org/wiki/Turingmaschinn" title="Turingmaschinn – luxembourgeois" lang="lb" hreflang="lb" data-title="Turingmaschinn" data-language-autonym="Lëtzebuergesch" data-language-local-name="luxembourgeois" class="interlanguage-link-target"><span>Lëtzebuergesch</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Macchina_del_Turing" title="Macchina del Turing – lombard" lang="lmo" hreflang="lmo" data-title="Macchina del Turing" data-language-autonym="Lombard" data-language-local-name="lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Tiuringo_ma%C5%A1ina" title="Tiuringo mašina – lituanien" lang="lt" hreflang="lt" data-title="Tiuringo mašina" data-language-autonym="Lietuvių" data-language-local-name="lituanien" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Tj%C5%ABringa_ma%C5%A1%C4%ABna" title="Tjūringa mašīna – letton" lang="lv" hreflang="lv" data-title="Tjūringa mašīna" data-language-autonym="Latviešu" data-language-local-name="letton" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%A2%D1%98%D1%83%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D0%B0_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0" title="Тјурингова машина – macédonien" lang="mk" hreflang="mk" data-title="Тјурингова машина" data-language-autonym="Македонски" data-language-local-name="macédonien" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%9F%E0%B5%82%E0%B4%B1%E0%B4%BF%E0%B4%99%E0%B5%8D_%E0%B4%AE%E0%B5%86%E0%B4%B7%E0%B5%80%E0%B5%BB" title="ടൂറിങ് മെഷീൻ – malayalam" lang="ml" hreflang="ml" data-title="ടൂറിങ് മെഷീൻ" data-language-autonym="മലയാളം" data-language-local-name="malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-mwl mw-list-item"><a href="https://mwl.wikipedia.org/wiki/M%C3%A1quina_de_Turing" title="Máquina de Turing – mirandais" lang="mwl" hreflang="mwl" data-title="Máquina de Turing" data-language-autonym="Mirandés" data-language-local-name="mirandais" class="interlanguage-link-target"><span>Mirandés</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Turingmachine" title="Turingmachine – néerlandais" lang="nl" hreflang="nl" data-title="Turingmachine" data-language-autonym="Nederlands" data-language-local-name="néerlandais" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Turingmaskin" title="Turingmaskin – norvégien nynorsk" lang="nn" hreflang="nn" data-title="Turingmaskin" data-language-autonym="Norsk nynorsk" data-language-local-name="norvégien nynorsk" class="interlanguage-link-target"><span>Norsk nynorsk</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Turingmaskin" title="Turingmaskin – norvégien bokmål" lang="nb" hreflang="nb" data-title="Turingmaskin" data-language-autonym="Norsk bokmål" data-language-local-name="norvégien bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-oc mw-list-item"><a href="https://oc.wikipedia.org/wiki/Maquina_de_Turing" title="Maquina de Turing – occitan" lang="oc" hreflang="oc" data-title="Maquina de Turing" data-language-autonym="Occitan" data-language-local-name="occitan" class="interlanguage-link-target"><span>Occitan</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Maszyna_Turinga" title="Maszyna Turinga – polonais" lang="pl" hreflang="pl" data-title="Maszyna Turinga" data-language-autonym="Polski" data-language-local-name="polonais" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/M%C3%A1quina_de_Turing" title="Máquina de Turing – portugais" lang="pt" hreflang="pt" data-title="Máquina de Turing" data-language-autonym="Português" data-language-local-name="portugais" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Ma%C8%99in%C4%83_Turing" title="Mașină Turing – roumain" lang="ro" hreflang="ro" data-title="Mașină Turing" data-language-autonym="Română" data-language-local-name="roumain" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0" title="Машина Тьюринга – russe" lang="ru" hreflang="ru" data-title="Машина Тьюринга" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Turingov_stroj" title="Turingov stroj – serbo-croate" lang="sh" hreflang="sh" data-title="Turingov stroj" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbo-croate" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Turing_machine" title="Turing machine – Simple English" lang="en-simple" hreflang="en-simple" data-title="Turing machine" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Turingov_stroj" title="Turingov stroj – slovaque" lang="sk" hreflang="sk" data-title="Turingov stroj" data-language-autonym="Slovenčina" data-language-local-name="slovaque" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Turingov_stroj" title="Turingov stroj – slovène" lang="sl" hreflang="sl" data-title="Turingov stroj" data-language-autonym="Slovenščina" data-language-local-name="slovène" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-sq mw-list-item"><a href="https://sq.wikipedia.org/wiki/Makina_Turing" title="Makina Turing – albanais" lang="sq" hreflang="sq" data-title="Makina Turing" data-language-autonym="Shqip" data-language-local-name="albanais" class="interlanguage-link-target"><span>Shqip</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A2%D1%98%D1%83%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D0%B0_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0" title="Тјурингова машина – serbe" lang="sr" hreflang="sr" data-title="Тјурингова машина" data-language-autonym="Српски / srpski" data-language-local-name="serbe" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Turingmaskin" title="Turingmaskin – suédois" lang="sv" hreflang="sv" data-title="Turingmaskin" data-language-autonym="Svenska" data-language-local-name="suédois" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%84%E0%B8%A3%E0%B8%B7%E0%B9%88%E0%B8%AD%E0%B8%87%E0%B8%97%E0%B8%B1%E0%B8%A7%E0%B8%A3%E0%B8%B4%E0%B8%87" title="เครื่องทัวริง – thaï" lang="th" hreflang="th" data-title="เครื่องทัวริง" data-language-autonym="ไทย" data-language-local-name="thaï" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Makinang_Turing" title="Makinang Turing – tagalog" lang="tl" hreflang="tl" data-title="Makinang Turing" data-language-autonym="Tagalog" data-language-local-name="tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Turing_makinesi" title="Turing makinesi – turc" lang="tr" hreflang="tr" data-title="Turing makinesi" data-language-autonym="Türkçe" data-language-local-name="turc" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8E%D1%80%D1%96%D0%BD%D0%B3%D0%B0" title="Машина Тюрінга – ukrainien" lang="uk" hreflang="uk" data-title="Машина Тюрінга" data-language-autonym="Українська" data-language-local-name="ukrainien" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/M%C3%A1y_Turing" title="Máy Turing – vietnamien" lang="vi" hreflang="vi" data-title="Máy Turing" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamien" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-wuu mw-list-item"><a href="https://wuu.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA" title="图灵机 – wu" lang="wuu" hreflang="wuu" data-title="图灵机" data-language-autonym="吴语" data-language-local-name="wu" class="interlanguage-link-target"><span>吴语</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA" title="图灵机 – chinois" lang="zh" hreflang="zh" data-title="图灵机" data-language-autonym="中文" data-language-local-name="chinois" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zh-min-nan mw-list-item"><a href="https://zh-min-nan.wikipedia.org/wiki/Turing_ki-h%C3%A2i" title="Turing ki-hâi – minnan" lang="nan" hreflang="nan" data-title="Turing ki-hâi" data-language-autonym="閩南語 / Bân-lâm-gú" data-language-local-name="minnan" class="interlanguage-link-target"><span>閩南語 / Bân-lâm-gú</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%9C%96%E9%9D%88%E6%A9%9F" title="圖靈機 – cantonais" lang="yue" hreflang="yue" data-title="圖靈機" data-language-autonym="粵語" data-language-local-name="cantonais" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q163310#sitelinks-wikipedia" title="Modifier les liens interlangues" class="wbc-editpage">Modifier les liens</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Espaces de noms"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Machine_de_Turing" title="Voir le contenu de la page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussion:Machine_de_Turing" rel="discussion" title="Discussion au sujet de cette page de contenu [t]" accesskey="t"><span>Discussion</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Modifier la variante de langue" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">français</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Affichages"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Machine_de_Turing"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&action=history" title="Historique des versions de cette page [h]" accesskey="h"><span>Voir l’historique</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Outils" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Outils</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Outils</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">masquer</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Plus d’options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Machine_de_Turing"><span>Lire</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&action=history"><span>Voir l’historique</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Général </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_li%C3%A9es/Machine_de_Turing" title="Liste des pages liées qui pointent sur celle-ci [j]" accesskey="j"><span>Pages liées</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Suivi_des_liens/Machine_de_Turing" rel="nofollow" title="Liste des modifications récentes des pages appelées par celle-ci [k]" accesskey="k"><span>Suivi des pages liées</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Aide:Importer_un_fichier" title="Téléverser des fichiers [u]" accesskey="u"><span>Téléverser un fichier</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_sp%C3%A9ciales" title="Liste de toutes les pages spéciales [q]" accesskey="q"><span>Pages spéciales</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&oldid=219498690" title="Adresse permanente de cette version de cette page"><span>Lien permanent</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&action=info" title="Davantage d’informations sur cette page"><span>Informations sur la page</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Citer&page=Machine_de_Turing&id=219498690&wpFormIdentifier=titleform" title="Informations sur la manière de citer cette page"><span>Citer cette page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:UrlShortener&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FMachine_de_Turing"><span>Obtenir l'URL raccourcie</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:QrCode&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FMachine_de_Turing"><span>Télécharger le code QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Imprimer / exporter </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Livre&bookcmd=book_creator&referer=Machine+de+Turing"><span>Créer un livre</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:DownloadAsPdf&page=Machine_de_Turing&action=show-download-screen"><span>Télécharger comme PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Machine_de_Turing&printable=yes" title="Version imprimable de cette page [p]" accesskey="p"><span>Version imprimable</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Dans d’autres projets </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Turing_Machine" hreflang="en"><span>Wikimedia Commons</span></a></li><li class="wb-otherproject-link wb-otherproject-wikiversity mw-list-item"><a href="https://fr.wikiversity.org/wiki/Calculabilit%C3%A9_et_complexit%C3%A9" hreflang="fr"><span>Wikiversité</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q163310" title="Lien vers l’élément dans le dépôt de données connecté [g]" accesskey="g"><span>Élément Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Apparence</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">masquer</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Un article de Wikipédia, l'encyclopédie libre.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"><span class="mw-redirectedfrom">(Redirigé depuis <a href="/w/index.php?title=Machines_de_Turing&redirect=no" class="mw-redirect" title="Machines de Turing">Machines de Turing</a>)</span></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><div class="bandeau-container metadata homonymie hatnote"><div class="bandeau-cell bandeau-icone" style="display:table-cell;padding-right:0.5em"><span class="noviewer" typeof="mw:File"><a href="/wiki/Aide:Homonymie" title="Aide:Homonymie"><img alt="Page d’aide sur l’homonymie" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png" decoding="async" width="20" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/30px-Logo_disambig.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/40px-Logo_disambig.svg.png 2x" data-file-width="512" data-file-height="375" /></a></span></div><div class="bandeau-cell" style="display:table-cell;padding-right:0.5em"> <p>Pour les articles homonymes, voir <a href="/wiki/Turing" class="mw-disambig" title="Turing">Turing</a>. </p> </div></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Hi%C3%A9rarchie_d%27automates.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/330px-Hi%C3%A9rarchie_d%27automates.svg.png" decoding="async" width="330" height="248" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/495px-Hi%C3%A9rarchie_d%27automates.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Hi%C3%A9rarchie_d%27automates.svg/660px-Hi%C3%A9rarchie_d%27automates.svg.png 2x" data-file-width="800" data-file-height="600" /></a><figcaption>Fig. 1 : Une hiérarchie d'automates.</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Maquina.png" class="mw-file-description"><img alt="Vue d’artiste d’une Machine de Turing (sans la table de transition)" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/220px-Maquina.png" decoding="async" width="220" height="122" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/330px-Maquina.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/440px-Maquina.png 2x" data-file-width="1800" data-file-height="1000" /></a><figcaption>Fig. 2 : Vue d’artiste d’une machine de Turing : un ruban infini muni d'une tête de lecture/écriture. La machine dispose également d'une table de transition, non représentée sur l'image.</figcaption></figure> <p>En <a href="/wiki/Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a>, une <b>machine de Turing</b> est un modèle abstrait du fonctionnement des <a href="/wiki/Calculatrice_m%C3%A9canique" title="Calculatrice mécanique">appareils mécaniques de calcul</a>, tel un <a href="/wiki/Ordinateur" title="Ordinateur">ordinateur</a>. Ce modèle a été imaginé par <a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> en 1936, en vue de donner une définition précise au concept d’<a href="/wiki/Algorithmique" title="Algorithmique">algorithme</a> ou de « procédure mécanique ». Il est toujours largement utilisé en <a href="/wiki/Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a>, en particulier dans les domaines de la <a href="/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes" class="mw-redirect" title="Théorie de la complexité des algorithmes">complexité algorithmique</a> et de la <a href="/wiki/Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">calculabilité</a>. </p><p>À l'origine, le concept de machine de Turing, inventé avant l'ordinateur, était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un <a href="/wiki/Ensemble_fini" title="Ensemble fini">ensemble fini</a> de <a href="/wiki/Symbole" title="Symbole">symboles</a>. D'autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes élémentaires du type : « si vous êtes dans <span class="nowrap">l'état 42</span> et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans <span class="nowrap">l'état 17</span>, et regarder maintenant la case adjacente à droite ». </p><p>La <a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a> postule que tout problème de calcul fondé sur une procédure algorithmique peut être résolu par une machine de Turing. Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition précise des procédures algorithmiques. En revanche, il est possible de définir une notion de « système acceptable de programmation » et de démontrer que le pouvoir de tels systèmes est équivalent à celui des machines de Turing (ils sont <a href="/wiki/Turing-complet" title="Turing-complet">Turing-complets</a>). </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Définition"><span id="D.C3.A9finition"></span>Définition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=1" title="Modifier la section : Définition" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=1" title="Modifier le code source de la section : Définition"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Quoique son nom de « machine » puisse conduire à croire le contraire, une machine de Turing est un concept abstrait, c'est-à-dire un objet mathématique. Une machine de Turing comporte les éléments suivants : </p> <ol><li>Un <b>ruban infini</b> divisé en cases consécutives. Chaque case contient un symbole d'un <a href="/wiki/Alphabet" title="Alphabet">alphabet</a> fini donné. L'alphabet contient un symbole spécial appelé « symbole blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur illimitée vers la gauche ou vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases du ruban contiennent par défaut le « symbole blanc » ;</li> <li>Une <b>tête de lecture/écriture</b> qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban ;</li> <li>Un <b>registre d'état</b> qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution ;</li> <li>Une <b>table d'actions</b> qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple « <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leftarrow }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">←</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \leftarrow }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3c0fb4bce772117bbaf55b7ca1539ceff9ae218c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \leftarrow }"></span> » pour une case vers la gauche, « <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rightarrow }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">→</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/53e574cc3aa5b4bf5f3f5906caf121a378eef08b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \rightarrow }"></span> » pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.</li></ol> <div class="mw-heading mw-heading2"><h2 id="Définition_formelle"><span id="D.C3.A9finition_formelle"></span>Définition formelle</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=2" title="Modifier la section : Définition formelle" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=2" title="Modifier le code source de la section : Définition formelle"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Plusieurs définitions formelles proches les unes des autres peuvent être données d'une machine de Turing. L'une d'elles<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup>, relativement courante, est choisie ici. Une machine de Turing est un quintuplet <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Q,\Gamma ,q_{0},\delta ,F)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>Q</mi> <mo>,</mo> <mi mathvariant="normal">Γ</mi> <mo>,</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mi>δ</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (Q,\Gamma ,q_{0},\delta ,F)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/628bce9492fd4461d278770e0ea434d47b68a7a7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.117ex; height:2.843ex;" alt="{\displaystyle (Q,\Gamma ,q_{0},\delta ,F)}"></span> où : </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}"></span> est un ensemble fini d'<i>états</i> ;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.453ex; height:2.176ex;" alt="{\displaystyle \Gamma }"></span> est l'<i>alphabet de travail</i> des symboles de la bande, contenant <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> un symbole particulier (dit <i>blanc</i>), <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B\in \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> <mo>∈</mo> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B\in \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/480996c31985be1a21a44897af0125de72c8fb81" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.057ex; height:2.176ex;" alt="{\displaystyle B\in \Gamma }"></span> ;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{0}}"></span> est l'<i>état initial</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}\in Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>∈</mo> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{0}\in Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ad0e7ce55cfad982929c93e29139a65108c37263" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.77ex; height:2.509ex;" alt="{\displaystyle q_{0}\in Q}"></span> ;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{\leftarrow ,\rightarrow \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>:</mo> <mi>Q</mi> <mo>×</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">→</mo> <mi>Q</mi> <mo>×</mo> <mi mathvariant="normal">Γ</mi> <mo>×</mo> <mo fence="false" stretchy="false">{</mo> <mo stretchy="false">←</mo> <mo>,</mo> <mo stretchy="false">→</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{\leftarrow ,\rightarrow \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/967978412875d6d0a85ed80c658d6457a56b1409" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.71ex; height:2.843ex;" alt="{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{\leftarrow ,\rightarrow \}}"></span> est la <i>fonction de transition</i> ;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> est l'ensemble des <i>états acceptants</i> (ou finals<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup>, terminaux), <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F\subseteq Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> <mo>⊆</mo> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F\subseteq Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ada8f098adcf02f7a674d2a5f2dda5e4917881e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.678ex; height:2.509ex;" alt="{\displaystyle F\subseteq Q}"></span>.</li></ul> <p>Il s'agit d'un modèle de machine de Turing complète et déterministe ; i.e <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall q\in Q,\forall \gamma \in \Gamma ,\delta (q,\gamma )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∀</mi> <mi>q</mi> <mo>∈</mo> <mi>Q</mi> <mo>,</mo> <mi mathvariant="normal">∀</mi> <mi>γ</mi> <mo>∈</mo> <mi mathvariant="normal">Γ</mi> <mo>,</mo> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo>,</mo> <mi>γ</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \forall q\in Q,\forall \gamma \in \Gamma ,\delta (q,\gamma )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d5809d3fad0be7f3816c8bc42a2891909ab5c889" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.181ex; height:2.843ex;" alt="{\displaystyle \forall q\in Q,\forall \gamma \in \Gamma ,\delta (q,\gamma )}"></span> est définie et unique<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite_crochet">[</span>3<span class="cite_crochet">]</span></a></sup>. </p><p>Les flèches dans la définition de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span> représentent les deux déplacements possibles de la tête de lecture/écriture, à savoir le déplacement à gauche et le déplacement à droite. La signification de cette fonction de transition peut être expliquée sur l'exemple suivant : <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (q_{1},x)=(q_{2},y,\leftarrow )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo stretchy="false">(</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mi>y</mi> <mo>,</mo> <mo stretchy="false">←</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta (q_{1},x)=(q_{2},y,\leftarrow )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ce7113c440bdfb9ae6a3689e07c1c13a1cd88d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.859ex; height:2.843ex;" alt="{\displaystyle \delta (q_{1},x)=(q_{2},y,\leftarrow )}"></span> signifie que si la machine de Turing est dans l'état <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9daa41f6e8f78ea6bb5711d7ac97901ce564b94e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{1}}"></span> et qu'elle lit le symbole <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span>, alors elle écrit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}"></span> à la place de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span>, va dans l'état <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd2d05084feb02b8ba29b0673440fb673b102589" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{2}}"></span>, puis déplace sa tête de lecture vers la gauche. </p><p>Le fonctionnement de la machine de Turing est alors le suivant : à chaque étape de son calcul, la machine évolue en fonction de l'état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve la tête de lecture. Ces deux informations permettent la mise à jour de l'état de la machine grâce à la fonction de transition. À l'instant initial, la machine se trouve dans l'état <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{0}}"></span>, et le premier symbole du ruban est l'entrée du programme. La machine s'arrête lorsqu'elle rentre dans un état terminal. Le résultat du calcul est alors le mot formé par les symboles successivement lus par la machine. </p><p>On peut contraindre un alphabet des entrées possibles <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }"></span> dans la définition. On peut ainsi travailler plus précisément sur cet alphabet en réservant certains symboles de l'alphabet complet <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.453ex; height:2.176ex;" alt="{\displaystyle \Gamma }"></span> pour les étapes de calcul de la machine. En particulier, <span class="need_ref" title="Il semble que le terme "entrée" est ici utilisé à la fois pour désigner le symbole lu par la machine à l'état initial, et pour désigner l'ensemble des symboles lus jusqu'à l'état terminal (demandé le juin 2020)." style="cursor:help;">le symbole blanc <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}"></span> ne doit pas faire partie de l'entrée et peut donc définir la fin de cette dernière</span><sup class="need_ref_tag" style="padding-left:2px;"><a href="/wiki/Wikip%C3%A9dia:Style_encyclop%C3%A9dique#Clair" title="Wikipédia:Style encyclopédique">[pas clair]</a></sup>. </p><p>Le premier exemple ci-dessous utilise une version très légèrement différente de machine de Turing dans laquelle une machine s'arrête si elle est dans un état terminal et qu'elle lit un certain caractère sur le ruban (ici le symbole blanc). Le deuxième exemple ci-dessous est le premier exemple historique donné par Turing dans son article de 1936 : c'est une machine qui ne s'arrête pas. </p> <div class="mw-heading mw-heading2"><h2 id="Exemples">Exemples</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=3" title="Modifier la section : Exemples" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=3" title="Modifier le code source de la section : Exemples"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Doubler_le_nombre_de_‘1’"><span id="Doubler_le_nombre_de_.E2.80.981.E2.80.99"></span>Doubler le nombre de ‘1’</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=4" title="Modifier la section : Doubler le nombre de ‘1’" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=4" title="Modifier le code source de la section : Doubler le nombre de ‘1’"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La machine de Turing qui suit possède un alphabet {‘0’, ‘1’}, ‘0’ étant le « symbole blanc ». On suppose que le ruban contient une série de ‘1’, et que la tête de lecture/écriture se trouve initialement au-dessus du ‘1’ le plus à gauche. Cette machine a pour effet de doubler le nombre de ‘1’, en intercalant un ‘0’ entre les deux séries. Par exemple, « 111 » devient « 1110111 ».<br /> L’ensemble d’états possibles de la machine est {e1, e2, e3, e4, e5} et l’état initial est e1.<br /> La table d’actions est la suivante : </p> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exemple de table de transition </caption> <tbody><tr> <th scope="col">Ancien état</th> <th scope="col">Symbole lu</th> <th scope="col">Symbole écrit</th> <th scope="col">Mouvement</th> <th scope="col">Nouvel état </th></tr> <tr> <th scope="row" rowspan="2">e1</th> <th scope="row">0 </th> <td colspan="3" align="center"><i>(Arrêt)</i> </td></tr> <tr> <th scope="row">1 </th> <td>0</td> <td>Droite</td> <td>e2 </td></tr> <tr> <th scope="row" rowspan="2">e2</th> <th scope="row">1 </th> <td>1</td> <td>Droite</td> <td>e2 </td></tr> <tr> <th scope="row">0 </th> <td>0</td> <td>Droite</td> <td>e3 </td></tr> <tr> <th scope="row" rowspan="2">e3</th> <th scope="row">1 </th> <td>1</td> <td>Droite</td> <td>e3 </td></tr> <tr> <th scope="row">0 </th> <td>1</td> <td>Gauche</td> <td>e4 </td></tr> <tr> <th scope="row" rowspan="2">e4</th> <th scope="row">1 </th> <td>1</td> <td>Gauche</td> <td>e4 </td></tr> <tr> <th scope="row">0 </th> <td>0</td> <td>Gauche</td> <td>e5 </td></tr> <tr> <th scope="row" rowspan="2">e5</th> <th scope="row">1 </th> <td>1</td> <td>Gauche</td> <td>e5 </td></tr> <tr> <th scope="row">0 </th> <td>1</td> <td>Droite</td> <td>e1 </td></tr></tbody></table> <p>L’exécution de cette machine pour une série de deux '1' serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et rouges) :<br /> </p> <table> <tbody><tr> <td> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exécution (1) </caption> <tbody><tr> <th scope="col">Étape</th> <th scope="col">État</th> <th scope="col">Ruban </th></tr> <tr> <th scope="row">1 </th> <td>e1</td> <td><style data-mw-deduplicate="TemplateStyles:r216721251">.mw-parser-output .texte-rouge{color:var(--color-destructive,#ff0000)}html.skin-theme-clientpref-day .mw-parser-output .texte-rouge{color:#ff0000}</style><span class="texte-rouge"><b>1</b></span>1 </td></tr> <tr> <th scope="row">2 </th> <td>e2</td> <td>0<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>1</b></span> </td></tr> <tr> <th scope="row">3 </th> <td>e2</td> <td>01<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span> </td></tr> <tr> <th scope="row">4 </th> <td>e3</td> <td>010<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span> </td></tr></tbody></table> </td> <td> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exécution (2) </caption> <tbody><tr> <th scope="col">Étape</th> <th scope="col">État</th> <th scope="col">Ruban </th></tr> <tr> <th scope="row">5 </th> <td>e4</td> <td>01<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>1 </td></tr> <tr> <th scope="row">6 </th> <td>e5</td> <td>0<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>1</b></span>01 </td></tr> <tr> <th scope="row">7 </th> <td>e5</td> <td><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>101 </td></tr> <tr> <th scope="row">8 </th> <td>e1</td> <td>1<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>1</b></span>01 </td></tr></tbody></table> </td> <td> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exécution (3) </caption> <tbody><tr> <th scope="col">Étape</th> <th scope="col">État</th> <th scope="col">Ruban </th></tr> <tr> <th scope="row">9 </th> <td>e2</td> <td>10<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>1 </td></tr> <tr> <th scope="row">10 </th> <td>e3</td> <td>100<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>1</b></span> </td></tr> <tr> <th scope="row">11 </th> <td>e3</td> <td>1001<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span> </td></tr> <tr> <th scope="row">12 </th> <td>e4</td> <td>100<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>1</b></span>1 </td></tr></tbody></table> </td> <td> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exécution (4) </caption> <tbody><tr> <th scope="col">Étape</th> <th scope="col">État</th> <th scope="col">Ruban </th></tr> <tr> <th scope="row">13 </th> <td>e4</td> <td>10<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>11 </td></tr> <tr> <th scope="row">14 </th> <td>e5</td> <td>1<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>011 </td></tr> <tr> <th scope="row">15 </th> <td>e1</td> <td>11<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r216721251"><span class="texte-rouge"><b>0</b></span>11 </td></tr> <tr> <th scope="row">  </th> <td colspan="2" align="center"><i>(Arrêt)</i> </td></tr></tbody></table> </td></tr></tbody></table> <p>Le comportement de cette machine peut être décrit comme une boucle : </p> <ul><li>Elle démarre son exécution dans l’état e1, remplace le premier 1 par un 0.</li> <li>Puis elle utilise l’état e2 pour se déplacer vers la droite, en sautant les 1 (un seul dans cet exemple) jusqu'à rencontrer un 0 (ou un blanc), et passer dans l'état e3.</li> <li>L’état e3 est alors utilisé pour sauter la séquence suivante de 1 (initialement aucun) et remplacer le premier 0 rencontré par un 1.</li> <li>L'état e4 permet de revenir vers la gauche jusqu’à trouver un 0, et passer dans l’état e5.</li> <li>L'état e5 permet ensuite à nouveau de se déplacer vers la gauche jusqu’à trouver un 0, écrit au départ par l’état e1.</li> <li>La machine remplace alors ce 0 par un 1, se déplace d’une case vers la droite et passe à nouveau dans l’état e1 pour une nouvelle itération de la boucle.</li></ul> <p>Ce processus se répète jusqu’à ce que e1 tombe sur un 0 (c’est le 0 du milieu entre les deux séquences de 1) ; à ce moment, la machine s’arrête. </p> <div class="mw-heading mw-heading3"><h3 id="Calculer_un_tiers_en_binaire">Calculer un tiers en binaire</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=5" title="Modifier la section : Calculer un tiers en binaire" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=5" title="Modifier le code source de la section : Calculer un tiers en binaire"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Dans l'exemple qui suit, la machine de Turing possède un ruban vide et permet de construire la suite 01010101010101... </p> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exemple de table infinie </caption> <tbody><tr> <th scope="col">Ancien état</th> <th scope="col">Symbole écrit</th> <th scope="col">Mouvement</th> <th scope="col">Nouvel état </th></tr> <tr> <th scope="row">a </th> <td>0</td> <td>Droite</td> <td>b </td></tr> <tr> <th scope="row">b </th> <td>1</td> <td>Droite</td> <td>a </td></tr></tbody></table> <p>L’exécution de cette machine serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et <a href="/wiki/Magenta_(couleur)" title="Magenta (couleur)">magenta</a>) : </p> <table cellspacing="0" cellpadding="0" class="wikitable" style="border:1px solid #999999;border-collapse:collapse"> <caption>Exécution de la Machine infinie </caption> <tbody><tr> <th scope="col">Étape</th> <th scope="col">État</th> <th scope="col">Ruban </th></tr> <tr> <th scope="row">1 </th> <td>a</td> <td><span style="color:#ff00ff"><b>0</b></span> </td></tr> <tr> <th scope="row">2 </th> <td>b</td> <td>0<span style="color:#ff00ff"><b>1</b></span> </td></tr> <tr> <th scope="row">3 </th> <td>a</td> <td>01<span style="color:#ff00ff"><b>0</b></span> </td></tr> <tr> <th scope="row">4 </th> <td>b</td> <td>010<span style="color:#ff00ff"><b>1</b></span> </td></tr> <tr> <th scope="row">5 </th> <td>a</td> <td>0101<span style="color:#ff00ff"><b>0</b></span> </td></tr> <tr> <th scope="row">6 </th> <td>b</td> <td>01010<span style="color:#ff00ff"><b>1</b></span> </td></tr> <tr> <th scope="row">7 </th> <td>a</td> <td>010101<span style="color:#ff00ff"><b>0</b></span> </td></tr> <tr> <th scope="row">8 </th> <td>b</td> <td>0101010<span style="color:#ff00ff"><b>1</b></span> </td></tr> <tr> <th scope="row">... </th> <td>...</td> <td>01010101<span style="color:#ff00ff"><b>...</b></span> </td></tr></tbody></table> <p>Le comportement de cette machine peut être décrit comme une boucle infinie : </p> <ul><li>Elle démarre son exécution dans l’état a, ajoute un 0 et se déplace à droite.</li> <li>Puis elle passe à l'état b, ajoute un 1 et se déplace à droite.</li> <li>Elle revient dans l'état a et réitère la première étape.</li></ul> <p>Cette machine est la contrepartie du calcul de un tiers dont l'écriture en binaire est 0,010101010101...; en effet dans le système binaire <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.0101={\frac {1}{4}}+{\frac {1}{16}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0.0101</mn> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>16</mn> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0.0101={\frac {1}{4}}+{\frac {1}{16}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f32cf7a149d5ddd74ac025d685084881a44844de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.558ex; height:5.176ex;" alt="{\displaystyle 0.0101={\frac {1}{4}}+{\frac {1}{16}}}"></span> et </p><p> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.01010101...=\sum _{k=1}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}\sum _{k=0}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}*{\frac {4}{3}}={\frac {1}{3}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0.01010101...</mn> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> <mi mathvariant="normal">∞</mi> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>4</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>+</mo> <mi mathvariant="normal">∞</mi> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>4</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> </mrow> <mo>∗</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>4</mn> <mn>3</mn> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>3</mn> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0.01010101...=\sum _{k=1}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}\sum _{k=0}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}*{\frac {4}{3}}={\frac {1}{3}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/804178acb25b5a0434cfcbbd100dd4137a65c1b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:49.678ex; height:7.343ex;" alt="{\displaystyle 0.01010101...=\sum _{k=1}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}\sum _{k=0}^{+\infty }{\frac {1}{4^{k}}}={\frac {1}{4}}*{\frac {4}{3}}={\frac {1}{3}}}"></span> soit un tiers écrit dans le système binaire.</p><ul class="gallery mw-gallery-traditional"> <li class="gallerycaption">Deux exemples de machines de Turing donnés sous forme de schémas</li> <li class="gallerybox" style="width: 435px"> <div class="thumb" style="width: 430px; height: 430px;"><span typeof="mw:File"><a href="/wiki/Fichier:Calcul_pgcd.jpg" class="mw-file-description" title="Calcul du PGCD de deux entiers X et Y écrits en unaire, avec l'algorithme d'Euclide[4]."><img alt="Un schéma des états de la machine, et une explication du rôle de chaque état." src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Calcul_pgcd.jpg/336px-Calcul_pgcd.jpg" decoding="async" width="336" height="400" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/c/c0/Calcul_pgcd.jpg 1.5x" data-file-width="434" data-file-height="516" /></a></span></div> <div class="gallerytext">Calcul du <a href="/wiki/Plus_grand_commun_diviseur" title="Plus grand commun diviseur">PGCD</a> de deux entiers X et Y écrits en unaire, avec l'algorithme d'Euclide<sup id="cite_ref-iam_4-0" class="reference"><a href="#cite_note-iam-4"><span class="cite_crochet">[</span>4<span class="cite_crochet">]</span></a></sup>. </div> </li> <li class="gallerybox" style="width: 435px"> <div class="thumb" style="width: 430px; height: 430px;"><span typeof="mw:File"><a href="/wiki/Fichier:Bijection_N_plan.jpg" class="mw-file-description" title="Établir une bijection entre les entiers naturels et les points du plan de coordonnées entières et positives[4]."><img alt="Le graphe des états de la machine, un tableau de correspondance entre les 16 premiers entiers et paires d'entiers et la représentation graphique de cette bijection, qui parcours les paires en zig-zag : d'abord (0, 0) puis (0, 1) puis (1, 0) puis (0, 2) etc." src="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Bijection_N_plan.jpg/400px-Bijection_N_plan.jpg" decoding="async" width="400" height="267" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Bijection_N_plan.jpg/600px-Bijection_N_plan.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/57/Bijection_N_plan.jpg/800px-Bijection_N_plan.jpg 2x" data-file-width="825" data-file-height="550" /></a></span></div> <div class="gallerytext">Établir une bijection entre les entiers naturels et les points du plan de coordonnées entières et positives<sup id="cite_ref-iam_4-1" class="reference"><a href="#cite_note-iam-4"><span class="cite_crochet">[</span>4<span class="cite_crochet">]</span></a></sup>.</div> </li> </ul> <div class="mw-heading mw-heading2"><h2 id="Machines_de_Turing_universelles">Machines de Turing universelles</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=6" title="Modifier la section : Machines de Turing universelles" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=6" title="Modifier le code source de la section : Machines de Turing universelles"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="bandeau-container bandeau-section metadata bandeau-niveau-information"><div class="bandeau-cell bandeau-icone-css loupe">Article détaillé : <a href="/wiki/Machine_de_Turing_universelle" title="Machine de Turing universelle">Machine de Turing universelle</a>.</div></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Model_of_a_Turing_machine.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Model_of_a_Turing_machine.jpg/220px-Model_of_a_Turing_machine.jpg" decoding="async" width="220" height="165" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Model_of_a_Turing_machine.jpg/330px-Model_of_a_Turing_machine.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/ad/Model_of_a_Turing_machine.jpg/440px-Model_of_a_Turing_machine.jpg 2x" data-file-width="3264" data-file-height="2448" /></a><figcaption>Un modèle de la machine de Turing.</figcaption></figure> <p>Comme Alan Turing le montre dans son article fondateur, il est possible de créer une machine de Turing qu'on appelle « machine de Turing universelle » et qui est capable de « simuler » le comportement de n'importe quelle autre machine de Turing. « Simuler » signifie que si la machine de Turing universelle reçoit en entrée un codage d'une machine <i>T</i> et des données <i>D</i>, elle produit le même résultat que la machine <i>T</i> à laquelle on donnerait en entrée les données <i>D</i>. </p><p>Une machine de Turing universelle a la capacité de calculer tout ce qui est calculable : on dit alors qu'elle est <a href="/wiki/Turing-complet" title="Turing-complet">Turing-complète</a>. En lui fournissant le codage adéquat, elle peut simuler toute <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonction récursive</a>, analyser tout <a href="/wiki/Langage_r%C3%A9cursif" title="Langage récursif">langage récursif</a>, et accepter tout <a href="/wiki/Langage_partiellement_d%C3%A9cidable" class="mw-redirect" title="Langage partiellement décidable">langage partiellement décidable</a>. Selon la <a href="/wiki/Th%C3%A8se_de_Church-Turing" class="mw-redirect" title="Thèse de Church-Turing">thèse de Church-Turing</a>, les problèmes résolubles par une machine de Turing universelle sont exactement les problèmes résolubles par un <i>algorithme</i> ou par une <i>méthode concrète de calcul</i>. </p> <div class="mw-heading mw-heading2"><h2 id="Réalisation_d'une_machine_de_Turing"><span id="R.C3.A9alisation_d.27une_machine_de_Turing"></span>Réalisation d'une machine de Turing</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=7" title="Modifier la section : Réalisation d'une machine de Turing" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=7" title="Modifier le code source de la section : Réalisation d'une machine de Turing"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size mw-halign-left" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Machine_de_turing.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Machine_de_turing.jpg/220px-Machine_de_turing.jpg" decoding="async" width="220" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Machine_de_turing.jpg/330px-Machine_de_turing.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Machine_de_turing.jpg/440px-Machine_de_turing.jpg 2x" data-file-width="3928" data-file-height="2140" /></a><figcaption>La machine de Turing de Marc Raynaud.</figcaption></figure> <p>Une machine de Turing est un objet de pensée : son ruban est infini, et donc la mémoire d'une machine de Turing est infinie. Une machine de Turing n'engendre jamais de <a href="/wiki/Out_of_memory" title="Out of memory">débordement de mémoire</a>, contrairement à un ordinateur dont la mémoire est finie. En oubliant ce problème de mémoire, on peut <a href="/wiki/Simulation_informatique" title="Simulation informatique">simuler</a> une machine de Turing sur un ordinateur moderne. </p><p> Il est aussi possible de construire des machines de Turing purement mécaniques. La machine de Turing, objet de pensée, a pu ainsi être <a href="https://fr.wiktionary.org/wiki/r%C3%A9ifier" class="extiw" title="wikt:réifier">réifiée</a> à de nombreuses reprises en utilisant des techniques parfois assez originales, dont voici quelques exemples.</p><figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Lego_Turing_Machine.jpg" class="mw-file-description"><img alt="Illustration d’une réalisation de machine de Turing en Lego créée pour l’année Turing" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Lego_Turing_Machine.jpg/220px-Lego_Turing_Machine.jpg" decoding="async" width="220" height="147" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Lego_Turing_Machine.jpg/330px-Lego_Turing_Machine.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Lego_Turing_Machine.jpg/440px-Lego_Turing_Machine.jpg 2x" data-file-width="900" data-file-height="600" /></a><figcaption>La machine de Turing en Lego créée à l’occasion du projet Rubens de l'ENS-Lyon.</figcaption></figure> <ul><li>En <time class="nowrap" datetime="2011-04" data-sort-value="2011-04">avril 2011</time>, Jim MacArthur a réalisé une machine de Turing mécanique compacte, à 5 symboles, avec des billes comme support d'informations sur le ruban<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite_crochet">[</span>5<span class="cite_crochet">]</span></a></sup>.</li> <li>En <time class="nowrap" datetime="2012-03" data-sort-value="2012-03">mars 2012</time>, à l’occasion de l’<a href="/w/index.php?title=Ann%C3%A9e_Turing&action=edit&redlink=1" class="new" title="Année Turing (page inexistante)">année Turing</a> <a href="https://en.wikipedia.org/wiki/Alan_Turing_Year" class="extiw" title="en:Alan Turing Year"><span class="indicateur-langue" title="Article en anglais : « Alan Turing Year »">(en)</span></a>, une équipe d'étudiants de l'<a href="/wiki/%C3%89cole_normale_sup%C3%A9rieure_de_Lyon" title="École normale supérieure de Lyon">École normale supérieure de Lyon</a> a réalisé une machine de Turing entièrement faite de pièces <a href="/wiki/Lego" title="Lego">Lego</a> sans électronique<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite_crochet">[</span>6<span class="cite_crochet">]</span></a></sup><sup class="reference cite_virgule">,</sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite_crochet">[</span>7<span class="cite_crochet">]</span></a></sup>.</li> <li>En novembre 2013, Marc Raynaud élabore un prototype électromécanique de la machine de Turing à 3 symboles, 12 états et 100 cases sur le ruban. Il fonctionne à la fréquence de 1 Hertz<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite_crochet">[</span>8<span class="cite_crochet">]</span></a></sup>. Facilement transportable, ce prototype est utilisé régulièrement , dans le cadre de recherches algorithmiques, par des professeurs, des étudiants et des lycéens.</li></ul> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Machine_de_Turing_p%C3%A9dagogique.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Machine_de_Turing_p%C3%A9dagogique.jpg/220px-Machine_de_Turing_p%C3%A9dagogique.jpg" decoding="async" width="220" height="137" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Machine_de_Turing_p%C3%A9dagogique.jpg/330px-Machine_de_Turing_p%C3%A9dagogique.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e0/Machine_de_Turing_p%C3%A9dagogique.jpg/440px-Machine_de_Turing_p%C3%A9dagogique.jpg 2x" data-file-width="3093" data-file-height="1933" /></a><figcaption>Machine de Turing programmable avec 3 symboles et au plus 12 états.</figcaption></figure> <ul><li>En octobre 2020, une machine de Turing pédagogique conçue par Thierry Delattre (Dunkerque), programmable pour des algorithmes ayant au maximum 12 états et avec un alphabet de 3 symboles. 50 algorithmes peuvent être stockés en mémoire. Une version ayant 22 états et 8 symboles date de février 2021<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite_crochet">[</span>9<span class="cite_crochet">]</span></a></sup>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Références_et_bibliographie"><span id="R.C3.A9f.C3.A9rences_et_bibliographie"></span>Références et bibliographie</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=8" title="Modifier la section : Références et bibliographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=8" title="Modifier le code source de la section : Références et bibliographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Références"><span id="R.C3.A9f.C3.A9rences"></span>Références</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=9" title="Modifier la section : Références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=9" title="Modifier le code source de la section : Références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style=""><div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink noprint"><a href="#cite_ref-1">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="https://en.wikipedia.org/wiki/Harry_R._Lewis" class="extiw" title="en:Harry R. Lewis">Harry R. Lewis</a> et <a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a>, <i>Elements of the Theory of Computation</i>. <a href="/wiki/Prentice-Hall" class="mw-redirect" title="Prentice-Hall">Prentice-Hall</a>, 1982; second edition September 1997.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink noprint"><a href="#cite_ref-2">↑</a> </span><span class="reference-text"><a rel="nofollow" class="external text" href="http://www.cnrtl.fr/definition/final">« FINAL »</a>, CNRTL : <span class="citation">« En fait, il y a flottement entre <i>finals</i> et <i>finaux</i> : le <abbr class="abbr" title="Premier">1<sup>er</sup></abbr> semble être le plur. de la lang. cour. et des écrivains, le second celui des linguistes et des économistes »</span>.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink noprint"><a href="#cite_ref-3">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Perrot2019"><span class="ouvrage" id="Kévin_Perrot2019">Kévin Perrot, « <a rel="nofollow" class="external text" href="http://pageperso.lif.univ-mrs.fr/~kevin.perrot/documents/2018/calculabilite/Cours01_18.pdf"><cite style="font-style:normal;">Calculabilité. Cours 1 : machines de Turing</cite></a> », sur <span class="italique">univ-mrs.fr</span>, <time class="nowrap" datetime="2019" data-sort-value="2019">printemps 2019</time> <small style="line-height:1em;">(consulté en <time class="nowrap" datetime="2020-11" data-sort-value="2020-11">novembre 2020</time>)</small></span></span></span> </li> <li id="cite_note-iam-4"><span class="mw-cite-backlink noprint">↑ <sup><a href="#cite_ref-iam_4-0">a</a> et <a href="#cite_ref-iam_4-1">b</a></sup> </span><span class="reference-text"><a rel="nofollow" class="external text" href="https://images-archive.math.cnrs.fr/La-machine-de-Turing-4.html">Explications sur math.cnrs.fr</a></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink noprint"><a href="#cite_ref-5">↑</a> </span><span class="reference-text"><span class="ouvrage" id="MacArthur2012"><span class="ouvrage" id="Jim_MacArthur2012"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Jim MacArthur, « <a rel="nofollow" class="external text" href="http://srimech.blogspot.fr/search/label/turingmachine"><cite style="font-style:normal;" lang="en">Turing machine</cite></a> », sur <span class="italique">srimech.blogspot.fr</span>, <time class="nowrap" datetime="2012-06-08" data-sort-value="2012-06-08">8 juin 2012</time> <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2018-02-20" data-sort-value="2018-02-20">20 février 2018</time>)</small></span></span>.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink noprint"><a href="#cite_ref-6">↑</a> </span><span class="reference-text"><span class="ouvrage" id="2012">« <a rel="nofollow" class="external text" href="http://rubens.ens-lyon.fr/fr/"><cite style="font-style:normal;">Projet RUBENS</cite></a> », sur <span class="italique">rubens.ens-lyon.fr</span>, <time class="nowrap" datetime="2012-03" data-sort-value="2012-03">mars 2012</time> <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2018-02-20" data-sort-value="2018-02-20">20 février 2018</time>)</small></span>.</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink noprint"><a href="#cite_ref-7">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Monde2012"><span class="ouvrage" id="Le_Monde2012">David Larousserie, <a href="/wiki/Le_Monde" title="Le Monde">Le Monde</a>, « <a rel="nofollow" class="external text" href="https://www.lemonde.fr/sciences/article/2012/06/22/l-ordinateur-en-lego-inspire-par-alan-turing_1723058_1650684.html"><cite style="font-style:normal;">Une machine entièrement mécanique qui ne manque pas d'air</cite></a> », sur <span class="italique">lemonde.fr</span>, <time class="nowrap" datetime="2012-06-22" data-sort-value="2012-06-22">22 juin 2012</time> <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2018-02-20" data-sort-value="2018-02-20">20 février 2018</time>)</small></span></span>.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink noprint"><a href="#cite_ref-8">↑</a> </span><span class="reference-text"><span class="ouvrage">« <a rel="nofollow" class="external text" href="https://images-archive.math.cnrs.fr/La-machine-de-Turing-1.html"><cite style="font-style:normal;">Images des mathématiques</cite></a> », sur <span class="italique">images-archive.math.cnrs.fr</span> <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2024-07-03" data-sort-value="2024-07-03">3 juillet 2024</time>)</small></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink noprint"><a href="#cite_ref-9">↑</a> </span><span class="reference-text"><span class="ouvrage">« <a rel="nofollow" class="external text" href="https://machine-de-turing.fr/"><cite style="font-style:normal;">Machine de Turing – Codez puis faites exécuter des animations lumineuses attrayantes, des calculs mathématiques sur des nombres binaires, des séries de nombres, ou tout autre application que vous inventerez à loisir !</cite></a> » <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2021-03-19" data-sort-value="2021-03-19">19 mars 2021</time>)</small></span>.</span> </li> </ol></div> </div> <div class="mw-heading mw-heading3"><h3 id="Bibliographie">Bibliographie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=10" title="Modifier la section : Bibliographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=10" title="Modifier le code source de la section : Bibliographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><span title="Document utilisé pour la rédaction de l’article"><span typeof="mw:File"><span><img alt="Document utilisé pour la rédaction de l’article" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/20px-Icon_flat_design_plume.svg.png" decoding="async" width="20" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/30px-Icon_flat_design_plume.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/40px-Icon_flat_design_plume.svg.png 2x" data-file-width="330" data-file-height="158" /></span></span></span> : document utilisé comme source pour la rédaction de cet article. </p> <dl><dt>Manuels</dt></dl> <ul><li><span class="ouvrage" id="Carton2008"><span class="ouvrage" id="Olivier_Carton2008">Olivier Carton, <cite class="italique">Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques</cite>, Paris, <a href="/wiki/Vuibert" title="Vuibert">Vuibert</a>, <time>2008</time>, 237 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-2-7117-2077-4" title="Spécial:Ouvrages de référence/978-2-7117-2077-4"><span class="nowrap">978-2-7117-2077-4</span></a>, <a href="/wiki/Syst%C3%A8me_universitaire_de_documentation" title="Système universitaire de documentation">SUDOC</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://www.sudoc.fr/128299258">128299258</a></span>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Langages+formels%2C+calculabilit%C3%A9+et+complexit%C3%A9&rft.place=Paris&rft.pub=Vuibert&rft.stitle=licence+et+master+de+math%C3%A9matiques+ou+d%27informatique%2C+option+informatique+de+l%27agr%C3%A9gation+de+math%C3%A9matiques&rft.aulast=Carton&rft.aufirst=Olivier&rft.date=2008&rft.tpages=237&rft.isbn=978-2-7117-2077-4&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>.<span class="nowrap" title="Ouvrage utilisé pour la rédaction de l'article"> <span typeof="mw:File"><span><img alt="Ouvrage utilisé pour la rédaction de l'article" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/20px-Icon_flat_design_plume.svg.png" decoding="async" width="20" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/30px-Icon_flat_design_plume.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/40px-Icon_flat_design_plume.svg.png 2x" data-file-width="330" data-file-height="158" /></span></span></span></li> <li><span class="ouvrage" id="Autebert1992"><span class="ouvrage" id="Jean-Michel_Autebert1992">Jean-Michel Autebert, <cite class="italique">Calculabilité et décidabilité</cite>, Paris, Masson, <time>1992</time>, 118 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-2-225-82632-0" title="Spécial:Ouvrages de référence/978-2-225-82632-0"><span class="nowrap">978-2-225-82632-0</span></a>, <a href="/wiki/Syst%C3%A8me_universitaire_de_documentation" title="Système universitaire de documentation">SUDOC</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://www.sudoc.fr/002676494">002676494</a></span>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Calculabilit%C3%A9+et+d%C3%A9cidabilit%C3%A9&rft.place=Paris&rft.pub=Masson&rft.aulast=Autebert&rft.aufirst=Jean-Michel&rft.date=1992&rft.tpages=118&rft.isbn=978-2-225-82632-0&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>.<span class="nowrap" title="Ouvrage utilisé pour la rédaction de l'article"> <span typeof="mw:File"><span><img alt="Ouvrage utilisé pour la rédaction de l'article" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/20px-Icon_flat_design_plume.svg.png" decoding="async" width="20" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/30px-Icon_flat_design_plume.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/40px-Icon_flat_design_plume.svg.png 2x" data-file-width="330" data-file-height="158" /></span></span></span></li> <li><span class="ouvrage" id="Jacopin2009"><span class="ouvrage" id="Éric_Jacopin2009">Éric Jacopin, <cite class="italique">Les machines de Turing : Introduction à la caractérisation de la complexité d'un problème</cite>, Toulouse, <a href="/wiki/%C3%89ditions_C%C3%A9padu%C3%A8s" title="Éditions Cépaduès">Éditions Cépaduès</a>, <time>2009</time>, 264 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/978-2-85428-865-0" title="Spécial:Ouvrages de référence/978-2-85428-865-0"><span class="nowrap">978-2-85428-865-0</span></a>, <a href="/wiki/Syst%C3%A8me_universitaire_de_documentation" title="Système universitaire de documentation">SUDOC</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://www.sudoc.fr/132323214">132323214</a></span>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Les+machines+de+Turing&rft.place=Toulouse&rft.pub=%C3%89ditions+C%C3%A9padu%C3%A8s&rft.stitle=Introduction+%C3%A0+la+caract%C3%A9risation+de+la+complexit%C3%A9+d%27un+probl%C3%A8me&rft.aulast=Jacopin&rft.aufirst=%C3%89ric&rft.date=2009&rft.tpages=264&rft.isbn=978-2-85428-865-0&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>.<span class="nowrap" title="Ouvrage utilisé pour la rédaction de l'article"> <span typeof="mw:File"><span><img alt="Ouvrage utilisé pour la rédaction de l'article" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/20px-Icon_flat_design_plume.svg.png" decoding="async" width="20" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/30px-Icon_flat_design_plume.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Icon_flat_design_plume.svg/40px-Icon_flat_design_plume.svg.png 2x" data-file-width="330" data-file-height="158" /></span></span></span></li></ul> <dl><dt>Turing</dt></dl> <ul><li><span class="ouvrage" id="TuringGirard1995"><span class="ouvrage" id="Alan_TuringJean-Yves_Girard1995"><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> et <a href="/wiki/Jean-Yves_Girard" title="Jean-Yves Girard">Jean-Yves Girard</a>, <cite class="italique">La machine de Turing</cite>, Paris, Éditions du Seuil, <time>1995</time>, 192 <abbr class="abbr" title="pages">p.</abbr> <small>[<a href="/wiki/R%C3%A9f%C3%A9rence:La_machine_de_Turing" title="Référence:La machine de Turing">détail de l’édition</a>]</small> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/9782020369282" title="Spécial:Ouvrages de référence/9782020369282"><span class="nowrap">9782020369282</span></a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=La+machine+de+Turing&rft.place=Paris&rft.pub=%C3%89ditions+du+Seuil&rft.aulast=Turing&rft.aufirst=Alan&rft.au=Jean-Yves+Girard&rft.date=1995&rft.tpages=192&rft.isbn=9782020369282&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span> ; cet ouvrage comprend notamment une traduction en français (par Julien Basch et Patrice Blanchard) de l'article original, ainsi qu'une correction par <a href="/wiki/Emil_Post" title="Emil Post">Emil Post</a> des erreurs y figurant ;</li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <span class="ouvrage" id="Turing1936"><span class="ouvrage" id="Alan_Turing1936">Alan Turing, « <cite style="font-style:normal">On Computable Numbers, with an Application to the Entscheidungsproblem</cite> », <i>Proceedings of the London Mathematical Society, série 2</i>, <abbr class="abbr" title="volume">vol.</abbr> 45,‎ <time>1936</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">230-265</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=On+Computable+Numbers%2C+with+an+Application+to+the+Entscheidungsproblem&rft.jtitle=Proceedings+of+the+London+Mathematical+Society%2C+s%C3%A9rie+2&rft.aulast=Turing&rft.aufirst=Alan&rft.date=1936&rft.volume=45&rft.pages=230-265&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span> ;</li> <li><abbr class="abbr indicateur-langue" title="Langue : français">(fr)</abbr> <span class="ouvrage" id="Turing"><span class="ouvrage" id="Alan_Turing">Alan Turing, <cite class="italique">Précis of ‘Computable Numbers’</cite> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.turingarchive.org/browse.php/K/4">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Pr%C3%A9cis+of+%E2%80%98Computable+Numbers%E2%80%99&rft.aulast=Turing&rft.aufirst=Alan&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>. — <small>Un brouillon pour une Note aux Comptes-Rendus de l’académie des Sciences de Paris.</small></li></ul> <dl><dt>Kleene</dt></dl> <ul><li><span class="ouvrage" id="Cole_Kleene1952"><span class="ouvrage" id="Stephen_Cole_Kleene1952"><a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Cole Kleene</a>, <cite class="italique">Introduction to Metamathematics</cite>, Amsterdam, North-Holland, <time>1952</time>, x+550 <small style="line-height:1em;">(<a href="/wiki/Syst%C3%A8me_universitaire_de_documentation" title="Système universitaire de documentation">SUDOC</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://www.sudoc.fr/005505526">005505526</a></span>, <a rel="nofollow" class="external text" href="https://books.google.com/books?id=HZAjPwAACAAJ">présentation en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Metamathematics&rft.place=Amsterdam&rft.pub=North-Holland&rft.au=Stephen+Cole+Kleene&rft.date=1952&rft.tpages=x%2B550&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>  — Nombreuses réimpressions, en 1957, 1959, 1962, 1964, 1967, 1971, 1974, 1980, 1988, 1991, 1996, 2000, 2009 notamment par Wolters-Noordhoff (Groningen) <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/0720421039" title="Spécial:Ouvrages de référence/0720421039"><span class="nowrap">0720421039</span></a>)</small>, d'après la notice Sudoc. Nombreuses traductions.</li> <li><abbr class="abbr indicateur-langue" title="Langues : anglais et français">(en + fr)</abbr> <span class="ouvrage" id="Cole_Kleene1967"><span class="ouvrage" id="Stephen_Cole_Kleene1967">Stephen Cole Kleene, <cite class="italique">Mathematical Logic</cite>, <a href="/wiki/Dover_Publications" title="Dover Publications">Dover</a>, <time>1967</time><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Mathematical+Logic&rft.pub=Dover&rft.au=Stephen+Cole+Kleene&rft.date=1967&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span> — Réimpression Dover reprint, 2001, <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/0-486-42533-9" title="Spécial:Ouvrages de référence/0-486-42533-9"><span class="nowrap">0-486-42533-9</span></a>)</small>. Traduction française par <a href="/wiki/Jean_Largeault" title="Jean Largeault">Jean Largeault</a>, <i>Logique mathématique</i>, Armand Colin, 1971 et Gabay 1987 <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/2-87647-005-5" title="Spécial:Ouvrages de référence/2-87647-005-5"><span class="nowrap">2-87647-005-5</span></a>)</small>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Voir_aussi">Voir aussi</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=11" title="Modifier la section : Voir aussi" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=11" title="Modifier le code source de la section : Voir aussi"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r194021218">.mw-parser-output .autres-projets>.titre{text-align:center;margin:0.2em 0}.mw-parser-output .autres-projets>ul{margin:0;padding:0}.mw-parser-output .autres-projets>ul>li{list-style:none;margin:0.2em 0;text-indent:0;padding-left:24px;min-height:20px;text-align:left;display:block}.mw-parser-output .autres-projets>ul>li>a{font-style:italic}@media(max-width:720px){.mw-parser-output .autres-projets{float:none}}</style><div class="autres-projets boite-grise boite-a-droite noprint js-interprojets"> <p class="titre">Sur les autres projets Wikimedia :</p> <ul class="noarchive plainlinks"> <li class="commons"><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Turing_machines?uselang=fr">Machine de Turing</a>, sur <span class="project">Wikimedia Commons</span></li><li class="wiktionary"><a href="https://fr.wiktionary.org/wiki/machine_de_Turing" class="extiw" title="wikt:machine de Turing">machine de Turing</a>, <span class="nowrap">sur le <span class="project">Wiktionnaire</span></span></li><li class="wikiversity"><a href="https://fr.wikiversity.org/wiki/Calculabilit%C3%A9_et_complexit%C3%A9" class="extiw" title="v:Calculabilité et complexité">Calculabilité et complexité</a>, <span class="nowrap">sur <span class="project">Wikiversity</span></span></li> </ul> </div> <div class="mw-heading mw-heading3"><h3 id="Articles_connexes">Articles connexes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=12" title="Modifier la section : Articles connexes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=12" title="Modifier le code source de la section : Articles connexes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Machine_de_Turing_non_d%C3%A9terministe" title="Machine de Turing non déterministe">Machine de Turing non déterministe</a></li> <li><a href="/wiki/Machine_de_Turing_probabiliste" title="Machine de Turing probabiliste">Machine de Turing probabiliste</a></li> <li><a href="/wiki/Machine_de_Turing_alternante" title="Machine de Turing alternante">Machine de Turing alternante</a></li> <li><a href="/wiki/Machine_de_Turing_sym%C3%A9trique" title="Machine de Turing symétrique">Machine de Turing symétrique</a></li> <li><a href="/wiki/Machine_de_Blum-Shub-Smale" title="Machine de Blum-Shub-Smale">Machine de Blum-Shub-Smale</a> : une généralisation à des machines calculant sur <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/786849c765da7a84dbc3cce43e96aad58a5868dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }"></span></li> <li><a href="/wiki/Probl%C3%A8me_de_la_d%C3%A9cision" title="Problème de la décision">Problème de la décision</a></li> <li><a href="/wiki/Exp%C3%A9rience_de_pens%C3%A9e" title="Expérience de pensée">Expérience de pensée</a></li> <li><a href="/wiki/Oracle_(machine_de_Turing)" title="Oracle (machine de Turing)">Oracle (machine de Turing)</a></li> <li><i><a href="/wiki/Imitation_Game" title="Imitation Game">Imitation Game</a></i>, film sur la vie d'<a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> avec <a href="/wiki/Benedict_Cumberbatch" title="Benedict Cumberbatch">Benedict Cumberbatch</a></li> <li><a href="/wiki/Fonction_constructible" title="Fonction constructible">Fonction constructible</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Liens_externes">Liens externes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Machine_de_Turing&veaction=edit&section=13" title="Modifier la section : Liens externes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Machine_de_Turing&action=edit&section=13" title="Modifier le code source de la section : Liens externes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Le film <a rel="nofollow" class="external text" href="http://videotheque.cnrs.fr/doc=3001">« La Machine de Turing réalisée »</a> de Christophe Gombert et Hugo Deboise à visionner en ligne gratuitement.</li> <li><a rel="nofollow" class="external text" href="http://smf.emath.fr/content/conf%C3%A9rence-bnf-2014-b-chazelle">Le génie interrompu d'Alan Turing</a> : présentation et bibliographie d'une conférence <a href="/wiki/Biblioth%C3%A8que_nationale_de_France" title="Bibliothèque nationale de France">BnF</a> de <a href="/wiki/Bernard_Chazelle" title="Bernard Chazelle">Bernard Chazelle</a>, programmée pour le <time class="nowrap" datetime="2014-03-19" data-sort-value="2014-03-19">19 mars 2014</time></li> <li><span class="ouvrage" id="Ben_Abdallah2013"><span class="ouvrage" id="Hamdi_Ben_Abdallah2013">Hamdi Ben Abdallah, « <cite style="font-style:normal">Comment fonctionne une machine de Turing ?</cite> », <i>Interstices</i>,‎ <time class="nowrap" datetime="2013-03-22" data-sort-value="2013-03-22">22 mars 2013</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://interstices.info/comment-fonctionne-une-machine-de-turing/">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Comment+fonctionne+une+machine+de+Turing+%3F&rft.jtitle=Interstices&rft.au=Hamdi+Ben+Abdallah&rft.date=2013-03-22&rfr_id=info%3Asid%2Ffr.wikipedia.org%3AMachine+de+Turing"></span></span></span>, <small>article permettant  d’essayer une machine de Turing.</small></li></ul> <div class="navbox-container" style="clear:both;"> <table class="navbox collapsible noprint autocollapse" style=""> <tbody><tr><th class="navbox-title" colspan="2" style=""><div style="float:left; width:6em; text-align:left"><div class="noprint plainlinks nowrap tnavbar" style="padding:0; font-size:xx-small; color:var(--color-emphasized, #000000);"><a href="/wiki/Mod%C3%A8le:Palette_Informatique_th%C3%A9orique" title="Modèle:Palette Informatique théorique"><abbr class="abbr" title="Voir ce modèle.">v</abbr></a> · <a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Mod%C3%A8le:Palette_Informatique_th%C3%A9orique&action=edit"><abbr class="abbr" title="Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.">m</abbr></a></div></div><div style="font-size:110%"><a href="/wiki/Informatique_th%C3%A9orique" title="Informatique théorique">Informatique théorique</a></div></th> </tr> <tr> <th class="navbox-group" style="">Codage</th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Codage_de_l%27information" title="Codage de l'information">Codage de l'information</a></li> <li><a href="/wiki/Compression_de_donn%C3%A9es" title="Compression de données">Compression de données</a></li> <li><a href="/wiki/Chiffrement" title="Chiffrement">Chiffrement</a></li> <li><a href="/wiki/Cryptanalyse" title="Cryptanalyse">Cryptanalyse</a></li> <li><a href="/wiki/Cryptographie" title="Cryptographie">Cryptographie</a></li> <li><a href="/wiki/Th%C3%A9orie_de_l%27information" title="Théorie de l'information">Théorie de l'information</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Modèles de calcul</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Th%C3%A9orie_de_la_calculabilit%C3%A9" title="Théorie de la calculabilité">Calculabilité</a></li> <li><a href="/wiki/D%C3%A9cidabilit%C3%A9" title="Décidabilité">Décidabilité et indécidabilité</a></li> <li><a href="/wiki/Ensemble_r%C3%A9cursif" title="Ensemble récursif">Ensemble récursif</a></li> <li><a href="/wiki/Probl%C3%A8me_de_l%27arr%C3%AAt" title="Problème de l'arrêt">Problème de l'arrêt</a></li> <li><a href="/wiki/R%C3%A9cursivement_%C3%A9num%C3%A9rable" title="Récursivement énumérable">Ensemble récursivement énumérable</a></li> <li><a class="mw-selflink selflink">Machine de Turing</a></li> <li><a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">Thèse de Church</a></li> <li><a href="/wiki/Automate_cellulaire" title="Automate cellulaire">Automate cellulaire</a></li> <li><a href="/wiki/R%C3%A9seau_de_neurones_artificiels" title="Réseau de neurones artificiels">Réseau de neurones artificiels</a></li> <li><a href="/wiki/R%C3%A9duction_polynomiale" title="Réduction polynomiale">Réduction polynomiale</a></li> <li><a href="/wiki/Cat%C3%A9gorie:Probl%C3%A8me_NP-complet" title="Catégorie:Problème NP-complet">Problème NP-complet</a></li> <li><a href="/wiki/Principe_de_Church-Turing-Deutsch" title="Principe de Church-Turing-Deutsch">Principe de Church-Turing-Deutsch</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Algorithmique" title="Algorithmique">Algorithmique</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Algorithmique" title="Algorithmique">Algorithmique</a></li> <li><a href="/wiki/Algorithme_glouton" title="Algorithme glouton">Algorithme glouton</a></li> <li><a href="/wiki/Algorithme_probabiliste" title="Algorithme probabiliste">Algorithme probabiliste</a></li> <li><a href="/wiki/Algorithme_g%C3%A9n%C3%A9tique" title="Algorithme génétique">Algorithme génétique</a></li> <li><a href="/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_(informatique_th%C3%A9orique)" title="Théorie de la complexité (informatique théorique)">Complexité algorithmique</a></li> <li><a href="/wiki/Analyse_de_la_complexit%C3%A9_des_algorithmes" title="Analyse de la complexité des algorithmes">Analyse d'algorithme</a></li> <li><a href="/wiki/Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">Diviser pour régner</a></li> <li><a href="/wiki/Heuristique_(math%C3%A9matiques)" title="Heuristique (mathématiques)">Heuristique</a></li> <li><a href="/wiki/Programmation_dynamique" title="Programmation dynamique">Programmation dynamique</a></li> <li><a href="/wiki/G%C3%A9om%C3%A9trie_algorithmique" title="Géométrie algorithmique">Géométrie algorithmique</a></li> <li><a href="/wiki/Algorithme_de_tri" title="Algorithme de tri">Algorithmes de tri</a></li> <li><a href="/wiki/Algorithmique_du_texte" title="Algorithmique du texte">Algorithmique du texte</a></li> <li><a href="/wiki/Exploration_de_donn%C3%A9es" title="Exploration de données">Exploration de données</a></li> <li><a href="/wiki/Science_des_donn%C3%A9es" title="Science des données">Science des données</a></li> <li><a href="/wiki/Apprentissage_profond" title="Apprentissage profond">Apprentissage profond</a></li> <li><a href="/wiki/Test_de_primalit%C3%A9" title="Test de primalité">Test de primalité</a></li> <li><a href="/wiki/Structure_de_donn%C3%A9es" title="Structure de données">Structure de données</a></li> <li><a href="/wiki/Arbre_enracin%C3%A9" title="Arbre enraciné">Arbre enraciné</a></li> <li><a href="/wiki/Programmation_concurrente" title="Programmation concurrente">Concurrence</a></li> <li><a href="/wiki/Parall%C3%A9lisme_(informatique)" title="Parallélisme (informatique)">Parallélisme</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Syntaxe</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/R%C3%A9%C3%A9criture_(informatique)" title="Réécriture (informatique)">Réécriture</a></li> <li><a href="/wiki/Compilateur" title="Compilateur">Compilation</a></li> <li><a href="/wiki/Expression_r%C3%A9guli%C3%A8re" title="Expression régulière">Expression régulière</a></li> <li><a href="/wiki/Grammaire_formelle" title="Grammaire formelle">Grammaire formelle</a></li> <li><a href="/wiki/Langage_rationnel" title="Langage rationnel">Langage rationnel</a></li> <li><a href="/wiki/Ensemble_rationnel" title="Ensemble rationnel">Ensemble rationnel</a></li> <li><a href="/wiki/Langage_formel" title="Langage formel">Théorie des langages</a></li> <li><a href="/wiki/Th%C3%A9orie_des_automates" title="Théorie des automates">Théorie des automates</a></li> <li><a href="/wiki/Automate_fini" title="Automate fini">Automate fini</a></li> <li><a href="/wiki/Automate_sur_les_mots_infinis" title="Automate sur les mots infinis">Automate sur les mots infinis</a></li> <li><a href="/wiki/Automate_d%27arbres" title="Automate d'arbres">Automate d'arbres</a></li> <li><a href="/wiki/Automate_%C3%A0_pile" title="Automate à pile">Automate à pile</a></li> <li><a href="/wiki/Hi%C3%A9rarchie_de_Chomsky" title="Hiérarchie de Chomsky">Hiérarchie de Chomsky</a></li> <li><a href="/wiki/Linguistique_informatique" title="Linguistique informatique">Linguistique informatique</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Sémantique</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Interpr%C3%A9tation_abstraite" title="Interprétation abstraite">Interprétation abstraite</a></li> <li><a href="/wiki/M%C3%A9thode_formelle_(informatique)" title="Méthode formelle (informatique)">Méthodes formelles</a></li> <li><a href="/wiki/V%C3%A9rification_de_mod%C3%A8les" title="Vérification de modèles">Vérification de modèles</a></li> <li><a href="/wiki/S%C3%A9mantique_des_langages_de_programmation" title="Sémantique des langages de programmation">Sémantique des langages de programmation</a></li> <li><a href="/wiki/S%C3%A9mantique_d%C3%A9notationnelle" title="Sémantique dénotationnelle">Sémantique dénotationnelle</a></li> <li><a href="/wiki/S%C3%A9mantique_axiomatique" title="Sémantique axiomatique">Sémantique axiomatique</a></li> <li><a href="/wiki/S%C3%A9mantique_op%C3%A9rationnelle" title="Sémantique opérationnelle">Sémantique opérationnelle</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Logique_math%C3%A9matique" title="Logique mathématique">Logique mathématique</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Assistant_de_preuve" title="Assistant de preuve">Assistant de preuve</a></li> <li><a href="/wiki/Calcul_des_pr%C3%A9dicats" title="Calcul des prédicats">Calcul des prédicats</a></li> <li><a href="/wiki/Correspondance_de_Curry-Howard" title="Correspondance de Curry-Howard">Correspondance de Curry-Howard</a></li> <li><a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">Fonction récursive</a></li> <li><a href="/wiki/Lambda-calcul" title="Lambda-calcul">Lambda-calcul</a></li> <li><a href="/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del" title="Théorèmes d'incomplétude de Gödel">Théorèmes d'incomplétude de Gödel</a></li> <li><a href="/wiki/Th%C3%A9orie_des_types" title="Théorie des types">Théorie des types</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Math%C3%A9matiques_discr%C3%A8tes" title="Mathématiques discrètes">Mathématiques discrètes</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Combinatoire" title="Combinatoire">Combinatoire</a></li> <li><a href="/wiki/Algorithme_du_simplexe" title="Algorithme du simplexe">Algorithme du simplexe</a></li> <li><a href="/wiki/Optimisation_combinatoire" title="Optimisation combinatoire">Optimisation combinatoire</a></li> <li><a href="/wiki/Th%C3%A9orie_des_graphes" title="Théorie des graphes">Théorie des graphes</a></li> <li><a href="/wiki/Liste_des_algorithmes_de_la_th%C3%A9orie_des_graphes" title="Liste des algorithmes de la théorie des graphes">Algorithmes de la théorie des graphes</a></li> <li><a href="/wiki/Recherche_op%C3%A9rationnelle" title="Recherche opérationnelle">Recherche opérationnelle</a></li> <li><a href="/wiki/Th%C3%A9orie_de_la_d%C3%A9cision" title="Théorie de la décision">Théorie de la décision</a></li> <li><a href="/wiki/Analyse_num%C3%A9rique" title="Analyse numérique">Analyse numérique</a></li></ul> </div></td> </tr> </tbody></table> </div><ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Machine_de_Turing&oldid=219498690">https://fr.wikipedia.org/w/index.php?title=Machine_de_Turing&oldid=219498690</a> ».</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Cat%C3%A9gorie:Accueil" title="Catégorie:Accueil">Catégories</a> : <ul><li><a href="/wiki/Cat%C3%A9gorie:Logique_math%C3%A9matique" title="Catégorie:Logique mathématique">Logique mathématique</a></li><li><a href="/wiki/Cat%C3%A9gorie:Calculabilit%C3%A9" title="Catégorie:Calculabilité">Calculabilité</a></li><li><a href="/wiki/Cat%C3%A9gorie:Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes" title="Catégorie:Théorie de la complexité des algorithmes">Théorie de la complexité des algorithmes</a></li><li><a href="/wiki/Cat%C3%A9gorie:Th%C3%A9orie_des_automates" title="Catégorie:Théorie des automates">Théorie des automates</a></li><li><a href="/wiki/Cat%C3%A9gorie:Alan_Turing" title="Catégorie:Alan Turing">Alan Turing</a></li><li><a href="/wiki/Cat%C3%A9gorie:Mod%C3%A8les_de_calcul" title="Catégorie:Modèles de calcul">Modèles de calcul</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Cat%C3%A9gorie_Commons_avec_lien_local_identique_sur_Wikidata" title="Catégorie:Catégorie Commons avec lien local identique sur Wikidata">Catégorie Commons avec lien local identique sur Wikidata</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> La dernière modification de cette page a été faite le 16 octobre 2024 à 11:22.</li> <li id="footer-info-copyright"><span style="white-space: normal"><a href="/wiki/Wikip%C3%A9dia:Citation_et_r%C3%A9utilisation_du_contenu_de_Wikip%C3%A9dia" title="Wikipédia:Citation et réutilisation du contenu de Wikipédia">Droit d'auteur</a> : les textes sont disponibles sous <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">licence Creative Commons attribution, partage dans les mêmes conditions</a> ; d’autres conditions peuvent s’appliquer. Voyez les <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/fr">conditions d’utilisation</a> pour plus de détails, ainsi que les <a href="/wiki/Wikip%C3%A9dia:Cr%C3%A9dits_graphiques" title="Wikipédia:Crédits graphiques">crédits graphiques</a>. En cas de réutilisation des textes de cette page, voyez <a href="/wiki/Sp%C3%A9cial:Citer/Machine_de_Turing" title="Spécial:Citer/Machine de Turing">comment citer les auteurs et mentionner la licence</a>.<br /> Wikipedia® est une marque déposée de la <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a href="/wiki/501c" title="501c">501(c)(3)</a> du code fiscal des États-Unis.</span><br /></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/fr">Politique de confidentialité</a></li> <li id="footer-places-about"><a href="/wiki/Wikip%C3%A9dia:%C3%80_propos_de_Wikip%C3%A9dia">À propos de Wikipédia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikip%C3%A9dia:Avertissements_g%C3%A9n%C3%A9raux">Avertissements</a></li> <li id="footer-places-contact"><a href="//fr.wikipedia.org/wiki/Wikipédia:Contact">Contact</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code de conduite</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Développeurs</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fr.wikipedia.org">Statistiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Déclaration sur les témoins (cookies)</a></li> <li id="footer-places-mobileview"><a href="//fr.m.wikipedia.org/w/index.php?title=Machine_de_Turing&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Version mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5c59558b9d-jsksk","wgBackendResponseTime":126,"wgPageParseReport":{"limitreport":{"cputime":"0.346","walltime":"0.510","ppvisitednodes":{"value":2221,"limit":1000000},"postexpandincludesize":{"value":72349,"limit":2097152},"templateargumentsize":{"value":11405,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":15677,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 337.840 1 -total"," 21.33% 72.073 1 Modèle:Références"," 11.30% 38.168 1 Modèle:Autres_projets"," 10.30% 34.814 1 Modèle:Voir_homonymes"," 10.16% 34.318 1 Modèle:Palette"," 9.91% 33.465 1 Modèle:Portail"," 9.67% 32.678 1 Modèle:Méta_bandeau_de_note"," 9.19% 31.033 1 Modèle:Méta_bandeau"," 8.74% 29.533 2 Modèle:En"," 8.60% 29.056 3 Modèle:Indication_de_langue"]},"scribunto":{"limitreport-timeusage":{"value":"0.105","limit":"10.000"},"limitreport-memusage":{"value":5150151,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-74cc59cb9d-62zf8","timestamp":"20241128102700","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Machine de Turing","url":"https:\/\/fr.wikipedia.org\/wiki\/Machine_de_Turing","sameAs":"http:\/\/www.wikidata.org\/entity\/Q163310","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q163310","author":{"@type":"Organization","name":"Contributeurs aux projets Wikimedia"},"publisher":{"@type":"Organization","name":"Fondation Wikimedia, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-02-28T10:46:18Z","dateModified":"2024-10-16T10:22:02Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/4\/4f\/Hi%C3%A9rarchie_d%27automates.svg","headline":"mod\u00e8le abstrait du fonctionnement des appareils m\u00e9caniques de calcul, tel un ordinateur et sa m\u00e9moire"}</script> </body> </html>