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>Théorie de la calculabilité — 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":"4d9a3549-9a8a-40df-bc50-499ea0e6b3cc","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Théorie_de_la_calculabilité","wgTitle":"Théorie de la calculabilité","wgCurRevisionId":216878144,"wgRevisionId":216878144,"wgArticleId":70110,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article à référence nécessaire","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Portail:Logique/Articles liés","Portail:Sciences/Articles liés","Portail:Mathématiques/Articles liés","Calculabilité","Logique mathématique"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName": "Théorie_de_la_calculabilité","wgRelevantArticleId":70110,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Calculabilité","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/Th%C3%A9orie_de_la_calculabilit%C3%A9","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q818930", "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","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.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%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.4"> <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 name="viewport" content="width=1120"> <meta property="og:title" content="Théorie de la calculabilité — 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/Th%C3%A9orie_de_la_calculabilit%C3%A9"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&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/Th%C3%A9orie_de_la_calculabilit%C3%A9"> <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-Théorie_de_la_calculabilité rootpage-Théorie_de_la_calculabilité 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=Th%C3%A9orie+de+la+calculabilit%C3%A9" 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=Th%C3%A9orie+de+la+calculabilit%C3%A9" 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=Th%C3%A9orie+de+la+calculabilit%C3%A9" 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=Th%C3%A9orie+de+la+calculabilit%C3%A9" 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_d'une_fonction_calculable" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Définition_d'une_fonction_calculable"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Définition d'une fonction calculable</span> </div> </a> <ul id="toc-Définition_d'une_fonction_calculable-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Définition_d'un_nombre_calculable" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Définition_d'un_nombre_calculable"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Définition d'un nombre calculable</span> </div> </a> <ul id="toc-Définition_d'un_nombre_calculable-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Existence_de_fonctions_non_calculables" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Existence_de_fonctions_non_calculables"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Existence de fonctions non calculables</span> </div> </a> <ul id="toc-Existence_de_fonctions_non_calculables-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Histoire" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Histoire"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Histoire</span> </div> </a> <button aria-controls="toc-Histoire-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 Histoire</span> </button> <ul id="toc-Histoire-sublist" class="vector-toc-list"> <li id="toc-Développement_des_machines_à_calculer" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Développement_des_machines_à_calculer"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Développement des machines à calculer</span> </div> </a> <ul id="toc-Développement_des_machines_à_calculer-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Développement_de_la_théorie_de_la_calculabilité_et_des_modèles_de_calcul" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Développement_de_la_théorie_de_la_calculabilité_et_des_modèles_de_calcul"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Développement de la théorie de la calculabilité et des modèles de calcul</span> </div> </a> <ul id="toc-Développement_de_la_théorie_de_la_calculabilité_et_des_modèles_de_calcul-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Modèles_de_calcul" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Modèles_de_calcul"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Modèles de calcul</span> </div> </a> <ul id="toc-Modèles_de_calcul-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Organisations_professionnelles" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Organisations_professionnelles"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Organisations professionnelles</span> </div> </a> <ul id="toc-Organisations_professionnelles-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes_et_références" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes_et_références"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes et références</span> </div> </a> <ul id="toc-Notes_et_références-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliographie" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Bibliographie</span> </div> </a> <ul id="toc-Bibliographie-sublist" class="vector-toc-list"> </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">9</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">9.1</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-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">Théorie de la calculabilité</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 41 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-41" 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">41 langues</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%86%D8%B8%D8%B1%D9%8A%D8%A9_%D8%A7%D9%84%D8%AD%D8%B3%D9%88%D8%A8%D9%8A%D8%A9" 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-as mw-list-item"><a href="https://as.wikipedia.org/wiki/%E0%A6%95%E0%A6%AE%E0%A7%8D%E0%A6%AA%E0%A6%BF%E0%A6%89%E0%A6%9F%E0%A7%87%E0%A6%AC%E0%A6%BF%E0%A6%B2%E0%A6%BF%E0%A6%9F%E0%A6%BF_%E0%A6%A5%E0%A6%BF%E0%A6%AF%E0%A6%BC%E0%A7%B0%E0%A7%80" title="কম্পিউটেবিলিটি থিয়ৰী – assamais" lang="as" hreflang="as" data-title="কম্পিউটেবিলিটি থিয়ৰী" data-language-autonym="অসমীয়া" data-language-local-name="assamais" class="interlanguage-link-target"><span>অসমীয়া</span></a></li><li class="interlanguage-link interwiki-ast mw-list-item"><a href="https://ast.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilid%C3%A1" title="Teoría de la computabilidá – asturien" lang="ast" hreflang="ast" data-title="Teoría de la computabilidá" data-language-autonym="Asturianu" data-language-local-name="asturien" class="interlanguage-link-target"><span>Asturianu</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Hesablama_n%C9%99z%C9%99riyy%C9%99si" title="Hesablama nəzəriyyəsi – azerbaïdjanais" lang="az" hreflang="az" data-title="Hesablama nəzəriyyəsi" data-language-autonym="Azərbaycanca" data-language-local-name="azerbaïdjanais" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%98%D0%B7%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D0%BD%D0%B0_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F" 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-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%AA%E0%A6%B0%E0%A6%BF%E0%A6%97%E0%A6%A3%E0%A6%A8%E0%A7%80%E0%A6%AF%E0%A6%BC%E0%A6%A4%E0%A6%BE_%E0%A6%A4%E0%A6%A4%E0%A7%8D%E0%A6%A4%E0%A7%8D%E0%A6%AC_(%E0%A6%95%E0%A6%AE%E0%A7%8D%E0%A6%AA%E0%A6%BF%E0%A6%89%E0%A6%9F%E0%A6%BE%E0%A6%B0_%E0%A6%AC%E0%A6%BF%E0%A6%9C%E0%A7%8D%E0%A6%9E%E0%A6%BE%E0%A6%A8)" title="পরিগণনীয়তা তত্ত্ব (কম্পিউটার বিজ্ঞান) – bengali" lang="bn" hreflang="bn" data-title="পরিগণনীয়তা তত্ত্ব (কম্পিউটার বিজ্ঞান)" data-language-autonym="বাংলা" data-language-local-name="bengali" class="interlanguage-link-target"><span>বাংলা</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Teoria_de_la_computabilitat" title="Teoria de la computabilitat – catalan" lang="ca" hreflang="ca" data-title="Teoria de la computabilitat" data-language-autonym="Català" data-language-local-name="catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Teorie_vy%C4%8D%C3%ADslitelnosti" title="Teorie vyčíslitelnosti – tchèque" lang="cs" hreflang="cs" data-title="Teorie vyčíslitelnosti" 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-cv mw-list-item"><a href="https://cv.wikipedia.org/wiki/%D0%A8%D1%83%D1%82%D0%BB%D0%B0%D0%BD%D0%B0%D1%8F%D1%81%D0%BB%C4%83%D1%85_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B9%C4%95" title="Шутланаяслăх теорийĕ – tchouvache" lang="cv" hreflang="cv" data-title="Шутланаяслăх теорийĕ" data-language-autonym="Чӑвашла" data-language-local-name="tchouvache" class="interlanguage-link-target"><span>Чӑвашла</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Beregnelighed" title="Beregnelighed – danois" lang="da" hreflang="da" data-title="Beregnelighed" 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/Berechenbarkeitstheorie" title="Berechenbarkeitstheorie – allemand" lang="de" hreflang="de" data-title="Berechenbarkeitstheorie" 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%98%CE%B5%CF%89%CF%81%CE%AF%CE%B1_%CF%85%CF%80%CE%BF%CE%BB%CE%BF%CE%B3%CE%B9%CF%83%CE%B9%CE%BC%CF%8C%CF%84%CE%B7%CF%84%CE%B1%CF%82" 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/Computability_theory" title="Computability theory – anglais" lang="en" hreflang="en" data-title="Computability theory" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad" title="Teoría de la computabilidad – espagnol" lang="es" hreflang="es" data-title="Teoría de la computabilidad" 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-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Konputagarritasunaren_teoria" title="Konputagarritasunaren teoria – basque" lang="eu" hreflang="eu" data-title="Konputagarritasunaren teoria" 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%86%D8%B8%D8%B1%DB%8C%D9%87_%D8%B1%D8%A7%DB%8C%D8%A7%D9%86%D8%B4%E2%80%8C%D9%BE%D8%B0%DB%8C%D8%B1%DB%8C" 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/Laskettavuusteoria" title="Laskettavuusteoria – finnois" lang="fi" hreflang="fi" data-title="Laskettavuusteoria" data-language-autonym="Suomi" data-language-local-name="finnois" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Teor%C3%ADa_da_computabilidade" title="Teoría da computabilidade – galicien" lang="gl" hreflang="gl" data-title="Teoría da computabilidade" 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%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%A8%D7%A7%D7%95%D7%A8%D7%A1%D7%99%D7%94" 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/Teorija_izra%C4%8Dunljivosti_(ra%C4%8Dunarstvo)" title="Teorija izračunljivosti (računarstvo) – croate" lang="hr" hreflang="hr" data-title="Teorija izračunljivosti (računarstvo)" data-language-autonym="Hrvatski" data-language-local-name="croate" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Teorio_di_komputebleso" title="Teorio di komputebleso – ido" lang="io" hreflang="io" data-title="Teorio di komputebleso" 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/Teoria_della_calcolabilit%C3%A0" title="Teoria della calcolabilità – italien" lang="it" hreflang="it" data-title="Teoria della calcolabilità" 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/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E6%80%A7%E7%90%86%E8%AB%96" 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-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B3%84%EC%82%B0_%EA%B0%80%EB%8A%A5%EC%84%B1_%EC%9D%B4%EB%A1%A0" 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/Theoria_facultatis_calculandi" title="Theoria facultatis calculandi – latin" lang="la" hreflang="la" data-title="Theoria facultatis calculandi" data-language-autonym="Latina" data-language-local-name="latin" class="interlanguage-link-target"><span>Latina</span></a></li><li class="interlanguage-link interwiki-my mw-list-item"><a href="https://my.wikipedia.org/wiki/%E1%80%90%E1%80%BD%E1%80%80%E1%80%BA%E1%80%81%E1%80%BB%E1%80%80%E1%80%BA%E1%80%94%E1%80%AD%E1%80%AF%E1%80%84%E1%80%BA%E1%80%85%E1%80%BD%E1%80%99%E1%80%BA%E1%80%B8%E1%80%9E%E1%80%AE%E1%80%A1%E1%80%AD%E1%80%AF%E1%80%9B%E1%80%AE" title="တွက်ချက်နိုင်စွမ်းသီအိုရီ – birman" lang="my" hreflang="my" data-title="တွက်ချက်နိုင်စွမ်းသီအိုရီ" data-language-autonym="မြန်မာဘာသာ" data-language-local-name="birman" class="interlanguage-link-target"><span>မြန်မာဘာသာ</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Teoria_obliczalno%C5%9Bci" title="Teoria obliczalności – polonais" lang="pl" hreflang="pl" data-title="Teoria obliczalności" 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/Teoria_da_computabilidade" title="Teoria da computabilidade – portugais" lang="pt" hreflang="pt" data-title="Teoria da computabilidade" 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/Teoria_calculabilit%C4%83%C8%9Bii" title="Teoria calculabilității – roumain" lang="ro" hreflang="ro" data-title="Teoria calculabilității" 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%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8" 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/Teorija_izra%C4%8Dunljivosti_(ra%C4%8Dunarstvo)" title="Teorija izračunljivosti (računarstvo) – serbo-croate" lang="sh" hreflang="sh" data-title="Teorija izračunljivosti (računarstvo)" 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/Computability_theory" title="Computability theory – Simple English" lang="en-simple" hreflang="en-simple" data-title="Computability theory" 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/Te%C3%B3ria_vypo%C4%8D%C3%ADtate%C4%BEnosti" title="Teória vypočítateľnosti – slovaque" lang="sk" hreflang="sk" data-title="Teória vypočítateľnosti" 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-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%98%D0%B0_%D0%B8%D0%B7%D1%80%D0%B0%D1%87%D1%83%D0%BD%D1%99%D0%B8%D0%B2%D0%BE%D1%81%D1%82%D0%B8_(%D1%80%D0%B0%D1%87%D1%83%D0%BD%D0%B0%D1%80%D1%81%D1%82%D0%B2%D0%BE)" 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-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%84%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%93%E0%B9%84%E0%B8%94%E0%B9%89" 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/Teorya_ng_komputabilidad" title="Teorya ng komputabilidad – tagalog" lang="tl" hreflang="tl" data-title="Teorya ng komputabilidad" 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/Hesaplanabilirlik_teorisi" title="Hesaplanabilirlik teorisi – turc" lang="tr" hreflang="tr" data-title="Hesaplanabilirlik teorisi" 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%A2%D0%B5%D0%BE%D1%80%D1%96%D1%8F_%D0%BE%D0%B1%D1%87%D0%B8%D1%81%D0%BB%D1%8E%D0%B2%D0%B0%D0%BD%D0%BE%D1%81%D1%82%D1%96" 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/L%C3%BD_thuy%E1%BA%BFt_t%C3%ADnh_to%C3%A1n" title="Lý thuyết tính toán – vietnamien" lang="vi" hreflang="vi" data-title="Lý thuyết tính toán" 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-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%8F%AF%E8%AE%A1%E7%AE%97%E6%80%A7%E7%90%86%E8%AE%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-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%8F%AF%E9%81%8B%E7%AE%97%E5%BA%A6%E7%90%86%E8%AB%96" 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/Q818930#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/Th%C3%A9orie_de_la_calculabilit%C3%A9" 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:Th%C3%A9orie_de_la_calculabilit%C3%A9" 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/Th%C3%A9orie_de_la_calculabilit%C3%A9"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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/Th%C3%A9orie_de_la_calculabilit%C3%A9"><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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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/Th%C3%A9orie_de_la_calculabilit%C3%A9" 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/Th%C3%A9orie_de_la_calculabilit%C3%A9" 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=Th%C3%A9orie_de_la_calculabilit%C3%A9&oldid=216878144" 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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&id=216878144&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%2FTh%25C3%25A9orie_de_la_calculabilit%25C3%25A9"><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%2FTh%25C3%25A9orie_de_la_calculabilit%25C3%25A9"><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=Th%C3%A9orie+de+la+calculabilit%C3%A9"><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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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/Category:Computability_theory" hreflang="en"><span>Wikimedia Commons</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/Q818930" 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=Calculabilit%C3%A9&redirect=no" class="mw-redirect" title="Calculabilité">Calculabilité</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"><p>La <b>théorie de la calculabilité</b> (appelée aussi parfois <b>théorie de la récursion</b>) est un domaine de la <a href="/wiki/Logique_math%C3%A9matique" title="Logique mathématique">logique mathématique</a> et de l'<a href="/wiki/Informatique_th%C3%A9orique" title="Informatique théorique">informatique théorique</a> qui vise à identifier les limites de ce qui peut être calculé par un <a href="/wiki/Algorithme" title="Algorithme">algorithme</a>. Cette théorie s'est développée dans les années 1930 lorsqu'ont été proposées pour la première fois des définitions formelles d'un algorithme, et des méthodes pour montrer que certains problèmes ne peuvent pas être résolus algorithmiquement. </p><p>La calculabilité ne se préoccupe pas de l'efficacité des algorithmes, qui est l'objet de la <a href="/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_(informatique_th%C3%A9orique)" title="Théorie de la complexité (informatique théorique)">théorie de la complexité</a>, mais seulement de l'existence ou de la non-existence d'un algorithme qui résout un problème donné, sur un ordinateur idéalisé tel qu'une <a href="/wiki/Machine_de_Turing" title="Machine de Turing">machine de Turing</a>, démontrée équivalente en possibilités à tous les ordinateurs existants. </p><p>La notion la plus centrale de la calculabilité est celle de <i>fonction calculable</i>. Son intérêt est justifié par la <a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a>, qui affirme que les fonctions calculables avec la définition formelle correspondent exactement aux fonctions qui peuvent être calculées par un humain ou une machine, dans le monde physique. </p><p>Cependant, la calculabilité ne se limite pas à séparer les fonctions calculables des fonctions non-calculables, mais cherche aussi à comparer les fonctions non-calculables entre elles, en s'appuyant sur la notion de <a href="/wiki/R%C3%A9duction_(complexit%C3%A9)" title="Réduction (complexité)">réduction</a> pour affirmer (informellement) que certaines fonctions sont « plus incalculables » que d'autres. Les niveaux d'incalculabilité sont appelés <a href="/wiki/Degr%C3%A9_de_Turing" title="Degré de Turing">degrés de Turing</a>, et une partie de la calculabilité consiste à étudier leur structure. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Définition_d'une_fonction_calculable"><span id="D.C3.A9finition_d.27une_fonction_calculable"></span>Définition d'une fonction calculable</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=1" title="Modifier la section : Définition d'une fonction calculable" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=1" title="Modifier le code source de la section : Définition d'une fonction calculable"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Intuitivement, une fonction <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/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span> est une <a href="/wiki/Fonction_calculable" class="mw-redirect" title="Fonction calculable">fonction calculable</a> s'il existe une méthode précise qui, étant donné un argument <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>, permet d'obtenir l'image <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(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}"></span> en un nombre fini d'étapes. Plusieurs formalisations mathématiques de ce que peut être une <i>méthode</i> de calcul existent et on peut montrer qu'un grand nombre d'entre elles (<a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a>, <a href="/wiki/Machine_de_Turing" title="Machine de Turing">machine de Turing</a>, <a href="/wiki/Lambda-calcul" title="Lambda-calcul">lambda-calcul</a>, <a href="/wiki/Machine_%C3%A0_compteurs" title="Machine à compteurs">machine à compteurs</a>, <a href="/wiki/Automate_cellulaire" title="Automate cellulaire">automate cellulaire</a>, etc.) sont équivalentes, c'est-à-dire qu'elles définissent exactement les mêmes fonctions calculables. Formellement, une fonction calculable est donc une fonction calculable selon l'une de ces définitions, par exemple le lambda-calcul<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><sup class="reference cite_virgule">,</sup><sup id="cite_ref-origine_2-0" class="reference"><a href="#cite_note-origine-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup>. </p><p>La <a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a> énonce que les définitions mathématiques équivalentes ci-dessus capturent bien le concept intuitif de <i>méthode de calcul défini par des moyens finis</i>, dit d'une autre façon <span class="citation">« N'importe quel moyen raisonnable de formaliser la notion d'<span class="citation">« algorithme »</span> est, en fait, équivalent à la notion de machine de Turing »</span><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> <div class="mw-heading mw-heading2"><h2 id="Définition_d'un_nombre_calculable"><span id="D.C3.A9finition_d.27un_nombre_calculable"></span>Définition d'un nombre calculable</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=2" title="Modifier la section : Définition d'un nombre calculable" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=2" title="Modifier le code source de la section : Définition d'un nombre calculable"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> définit un <a href="/wiki/Nombre_r%C3%A9el_calculable" title="Nombre réel calculable">nombre réel calculable</a> comme étant un nombre dont l'expression décimale est calculable avec des moyens finis. Autrement dit, il existe une <a href="/wiki/Machine_de_Turing" title="Machine de Turing">machine de Turing</a> qui permet d'énumérer la suite de tous les chiffres de ce nombre (en un temps infini). </p><p>Par extension, un <a href="/wiki/Nombre_complexe" title="Nombre complexe">nombre complexe</a> est calculable si sa partie réelle et sa partie imaginaire sont simultanément calculables. </p> <div class="mw-heading mw-heading2"><h2 id="Existence_de_fonctions_non_calculables">Existence de fonctions non calculables</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=3" title="Modifier la section : Existence de fonctions non calculables" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=3" title="Modifier le code source de la section : Existence de fonctions non calculables"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Il peut être démontré qu'il existe des fonctions <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/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span> qui sont incalculables, c’est-à-dire dont, étant donné <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>, la valeur <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(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}"></span> ne peut être calculée par des moyens finis par aucun algorithme que l'on aurait associé à <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/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}"></span>. En effet, il y a un nombre <a href="/wiki/Ensemble_d%C3%A9nombrable" title="Ensemble dénombrable">dénombrable</a> d'algorithmes (un algorithme peut toujours être représenté par un mot fini sur un alphabet fini), donc il y a seulement un nombre dénombrable de fonctions calculables. En revanche, les fonctions (<a href="/wiki/Fonction_partielle" title="Fonction partielle">partielles</a> ou pas) sur un domaine infini ne sont pas dénombrables, par le <a href="/wiki/Th%C3%A9or%C3%A8me_de_Cantor" title="Théorème de Cantor">théorème de Cantor</a><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite_crochet">[</span>4<span class="cite_crochet">]</span></a></sup>. Ceci fournit une preuve de l'existence de fonctions incalculables. </p><p>On connaît de nombreux exemples explicites de fonctions incalculables. Le plus courant est celui du <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> : il n'existe pas de programme universel qui prenne n'importe quel programme en argument et qui, en temps fini, renvoie « oui » si l'exécution du programme reçu en argument finit par s'arrêter et « non » s'il ne finit pas. Un autre exemple d'une fonction non calculable, plus perturbante dans un certain sens, est celle dite du <a href="/wiki/Castor_affair%C3%A9" title="Castor affairé">castor affairé</a>. Il s'agit d'une fonction bien définie, ayant une valeur pour chaque entier, mais on ne peut pas la calculer pour les entiers suffisamment grands. <a href="/wiki/Gregory_Chaitin" title="Gregory Chaitin">Gregory Chaitin</a> a introduit un <a href="/wiki/Om%C3%A9ga_de_Chaitin" title="Oméga de Chaitin">nombre Ω</a> qui a, entre autres, la particularité d'être parfaitement défini, mais dont la suite des décimales ne peut pas être donnée par une fonction calculable. </p> <div class="mw-heading mw-heading2"><h2 id="Histoire">Histoire</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=4" title="Modifier la section : Histoire" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=4" title="Modifier le code source de la section : Histoire"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Alors que la notion intuitive de <a href="/wiki/Fonction_calculable" class="mw-redirect" title="Fonction calculable">fonction calculable</a> est aussi vieille que les mathématiques, la formalisation de ces notions a commencé dans la décennie 1930 (voir <a href="/wiki/Histoire_des_math%C3%A9matiques#Logique_et_théorie_des_ensembles" title="Histoire des mathématiques">Logique et théorie des ensembles</a>) afin de répondre à des problèmes fondamentaux de <a href="/wiki/Logique_math%C3%A9matique" title="Logique mathématique">logique mathématique</a>, dont celui énoncé par <a href="/wiki/David_Hilbert" title="David Hilbert">David Hilbert</a> et appelé <i><span class="lang-de" lang="de">Entscheidungsproblem</span></i> ou <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><sup id="cite_ref-origine_2-1" class="reference"><a href="#cite_note-origine-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup>. </p> <div class="mw-heading mw-heading3"><h3 id="Développement_des_machines_à_calculer"><span id="D.C3.A9veloppement_des_machines_.C3.A0_calculer"></span>Développement des machines à calculer</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=5" title="Modifier la section : Développement des machines à calculer" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=5" title="Modifier le code source de la section : Développement des machines à calculer"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/66/NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg/220px-NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg" decoding="async" width="220" height="196" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/66/NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg/330px-NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/66/NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg/440px-NAMA_Machine_d%27Anticyth%C3%A8re_1.jpg 2x" data-file-width="1036" data-file-height="924" /></a><figcaption>Le fragment principal de la machine d'Anticythère.</figcaption></figure> <p>Bien avant de théoriser ce qu’est la calculabilité, les scientifiques ont commencé à développer des machines à calculer. Ainsi, dans l'<a href="/wiki/Antiquit%C3%A9" title="Antiquité">Antiquité</a>, la <a href="/wiki/Machine_d%27Anticyth%C3%A8re" title="Machine d'Anticythère">machine d'Anticythère</a> date du <abbr class="abbr" title="1ᵉʳ siècle"><span class="romain">I</span><sup style="font-size:72%">er</sup></abbr> siècle <abbr class="abbr nowrap" title="avant Jésus-Christ">av. J.-C.</abbr><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><sup class="reference cite_virgule">,</sup><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>. </p><p>Dans une période plus récente, <a href="/wiki/Wilhelm_Schickard" title="Wilhelm Schickard">Wilhelm Schickard</a> a imaginé, au <abbr class="abbr" title="17ᵉ siècle"><span class="romain">XVII</span><sup style="font-size:72%">e</sup></abbr> siècle, une « machine » à calculer mécanique avec une horloge à calculer qui utiliserait un système de rouages. Cependant, ce projet dépassait les capacités techniques des artisans de l’époque et n’a jamais pu voir le jour<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>. </p><p>La première machine à calculer opérationnelle du <abbr class="abbr" title="17ᵉ siècle"><span class="romain">XVII</span><sup style="font-size:72%">e</sup></abbr> siècle est donc la <a href="/wiki/Pascaline" title="Pascaline">pascaline</a> de <a href="/wiki/Blaise_Pascal" title="Blaise Pascal">Blaise Pascal</a>. Elle utilise un système de <a href="/wiki/Engrenage#Lanternes_et_rouets" title="Engrenage">pignons lanternes</a> et permet de réaliser des calculs simples (<a href="/wiki/Addition" title="Addition">addition</a>, <a href="/wiki/Soustraction" title="Soustraction">soustraction</a>, <a href="/wiki/Multiplication" title="Multiplication">multiplication</a> et <a href="/wiki/Division" title="Division">division</a>)<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>. </p><p>Au <abbr class="abbr" title="19ᵉ siècle"><span class="romain">XIX</span><sup style="font-size:72%">e</sup></abbr> siècle, <a href="/wiki/Joseph_Marie_Jacquard" title="Joseph Marie Jacquard">Joseph Marie Jacquard</a> met au point le <a href="/wiki/M%C3%A9tier_Jacquard" title="Métier Jacquard">métier à tisser Jacquard</a>. Premier système mécanique programmable avec cartes perforées, il est à l’origine des premiers programmes de calculs<sup class="need_ref_tag" style="padding-left:2px; cursor:help;" title="Ce passage devrait préciser la personne ou l'organisation qui fait cette affirmation."><a href="/wiki/Aide:Qui" title="Aide:Qui">[Selon qui ?]</a></sup><sup class="need_ref_tag" style="padding-left:2px;"><a href="/wiki/Aide:R%C3%A9f%C3%A9rence_n%C3%A9cessaire" title="Aide:Référence nécessaire"><span title="Ce passage nécessite une référence (demandé le 26 avril 2021) ; voir l'aide.">[réf. nécessaire]</span></a></sup>. </p><p><a href="/wiki/Charles_Babbage" title="Charles Babbage">Charles Babbage</a> développe en 1821 une machine à calculer destinée au calcul de polynômes appelée <a href="/wiki/Charles_Babbage#La_machine_à_différences" title="Charles Babbage">la machine à différences</a>. En 1834, à partir de cette première machine, il développe la machine analytique en y incorporant les cartes du métier Jacquard. Cette machine analytique contient une <a href="/wiki/Unit%C3%A9_de_contr%C3%B4le" title="Unité de contrôle">unité de contrôle</a>, une unité de calcul, une mémoire et une entrée-sortie et préfigure les ordinateurs d’aujourd’hui (voir <a href="/wiki/Calculatrice_m%C3%A9canique#XIXe_siècle_-_Le_début_de_la_production_industrielle" title="Calculatrice mécanique"><abbr class="abbr" title="19ᵉ siècle"><span class="romain">XIX</span><sup style="font-size:72%">e</sup></abbr> siècle- Le début de la production industrielle (dans l'article <i>Calculatrice mécanique</i></a>). </p><p>Entre 1842 et 1843, <a href="/wiki/Ada_Lovelace" title="Ada Lovelace">Ada Lovelace</a> traduit un article sur la machine analytique de Babbage. Ce dernier lui propose alors d’ajouter des notes pour développer et commenter le texte. S’ensuivit une collaboration étroite entre les deux scientifiques. Elle ajouta finalement sept notes représentant trois fois le volume du texte original. Sa dernière note porte sur un véritable <a href="/wiki/Algorithme" title="Algorithme">algorithme</a> permettant de calculer les <a href="/wiki/Nombres_de_Bernoulli" class="mw-redirect" title="Nombres de Bernoulli">nombres de Bernoulli</a> avec la machine analytique. Le programme ainsi rédigé est considéré comme le premier véritable <a href="/wiki/Programme_informatique" title="Programme informatique">programme informatique</a> jamais écrit car on y trouve un langage destiné à être exécuté sur une machine. Ada Lovelace, en plus d’être la première programmeuse au monde, suggère que la machine est un calculateur universel, préfigurant la notion de calculabilité<sup class="need_ref_tag" style="padding-left:2px;"><a href="/wiki/Aide:R%C3%A9f%C3%A9rence_n%C3%A9cessaire" title="Aide:Référence nécessaire"><span title="Ce passage nécessite une référence ; voir l'aide.">[réf. nécessaire]</span></a></sup>. </p> <div class="mw-heading mw-heading3"><h3 id="Développement_de_la_théorie_de_la_calculabilité_et_des_modèles_de_calcul"><span id="D.C3.A9veloppement_de_la_th.C3.A9orie_de_la_calculabilit.C3.A9_et_des_mod.C3.A8les_de_calcul"></span>Développement de la théorie de la calculabilité et des modèles de calcul</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=6" title="Modifier la section : Développement de la théorie de la calculabilité et des modèles de calcul" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=6" title="Modifier le code source de la section : Développement de la théorie de la calculabilité et des modèles de calcul"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/David_Hilbert" title="David Hilbert">David Hilbert</a>, présente, lors du deuxième <a href="/wiki/Congr%C3%A8s_international_des_math%C3%A9maticiens" title="Congrès international des mathématiciens">congrès international des mathématiciens</a> tenu en 1900, une liste de <span class="nowrap">23 problèmes</span> que l’on appelle aujourd’hui les <a href="/wiki/Probl%C3%A8mes_de_Hilbert" title="Problèmes de Hilbert">problèmes de Hilbert</a>. Le <a href="/wiki/Dixi%C3%A8me_probl%C3%A8me_de_Hilbert" title="Dixième problème de Hilbert">dixième problème de Hilbert</a> s'énonce ainsi<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite_crochet">[</span>10<span class="cite_crochet">]</span></a></sup> : </p><p><span style="display: block; margin-left:1.6em;">« On se donne une <a href="/wiki/%C3%89quation_diophantienne" title="Équation diophantienne">équation diophantienne</a> à un nombre quelconque d'inconnues et à coefficients entiers rationnels : <i>On demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers rationnels.</i> »</span> </p><p>Ce problème requiert une méthode algorithmique générale qui décide si une <a href="/wiki/%C3%89quation_diophantienne" title="Équation diophantienne">équation diophantienne</a> possède des solutions entières. Il s’agit du seul des <span class="nowrap">23 problèmes</span> de Hilbert qui soit un <a href="/wiki/Probl%C3%A8me_de_d%C3%A9cision" title="Problème de décision">problème de décision</a>, c’est-à-dire un problème qui se décompose en une infinité de problèmes particuliers qui attendent une réponse par « oui » ou « non ». Une solution à un problème de décision est un <a href="/wiki/Algorithmique" title="Algorithmique">algorithme</a> qui, pour chaque entrée, fournit la réponse « oui » ou « non ». Cependant à l’époque où le dixième problème de Hilbert est formulé, il n’y a pas de définition rigoureuse de ce qu’est un algorithme. </p><p>De plus, à l’époque de la <a href="/wiki/Crise_des_fondements" title="Crise des fondements">crise des fondements</a> des mathématiques, David Hilbert s’oppose fermement à l’idée que certaines questions scientifiques restent sans réponse. Il croit au <a href="/wiki/Principe_du_tiers_exclu" title="Principe du tiers exclu">tiers exclu</a>, un principe logique qui affirme qu’une proposition est soit démontrable, soit sa négation est démontrable. Pour régler le problème de ces fondements, il rédige un programme (qu’on appelle aujourd’hui <a href="/wiki/Programme_de_Hilbert" title="Programme de Hilbert">programme de Hilbert</a>) dont il établit les prémices en 1900 dans l’introduction à sa liste de problèmes. Il développe ensuite ce programme dans les années 1920 avec l’aide de <a href="/wiki/Paul_Bernays" title="Paul Bernays">Paul Bernays</a> et <a href="/wiki/Wilhelm_Ackermann" title="Wilhelm Ackermann">Wilhelm Ackermann</a>. Son idée est que tant que ce que l’on manipule est fini, les mathématiques sont sûres. Pour justifier l'utilisation d'objets abstraits ou idéaux, en particulier infinis, il suffit de montrer que la théorie qui les utilise est cohérente, mais bien sûr cette cohérence doit elle-même être démontrée par des moyens finis. On appelle cette approche le « <a href="/wiki/Fondements_des_math%C3%A9matiques#Le_formalisme" title="Fondements des mathématiques">formalisme</a> ». </p><p><a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a> assiste à une conférence de David Hilbert sur la <a href="/wiki/Th%C3%A9or%C3%A8me_de_compl%C3%A9tude_de_G%C3%B6del" title="Théorème de complétude de Gödel">complétude</a> et la cohérence des systèmes mathématiques lorsqu’il est encore étudiant. Il obtient son doctorat en 1929 grâce à sa thèse où il établit la complétude du <a href="/wiki/Calcul_des_pr%C3%A9dicats_du_premier_ordre" class="mw-redirect" title="Calcul des prédicats du premier ordre">calcul des prédicats du premier ordre</a> (en termes intuitifs, ce théorème nous apporte que tout énoncé vrai est démontrable), résultat connu sous le nom de <a href="/wiki/Th%C3%A9or%C3%A8me_de_compl%C3%A9tude_de_G%C3%B6del" title="Théorème de complétude de Gödel">théorème de complétude de Gödel</a>. Ce théorème va dans le sens de Hilbert. </p><p>Cependant, en 1931, il publie ses célèbres <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</a>. Il y montre que pour toute <a href="/wiki/Th%C3%A9orie_axiomatique" title="Théorie axiomatique">théorie axiomatique</a> non contradictoire de l'arithmétique, il existe des énoncés arithmétiques vrais qui ne sont pas démontrables dans cette théorie. Autrement dit, Gödel marque un tournant dans l’<a href="/wiki/Histoire_de_la_logique" title="Histoire de la logique">histoire de la logique</a> puisqu’il anéantit la possibilité d'une démonstration de la cohérence des mathématiques énoncée vingt ans auparavant dans le <a href="/wiki/Programme_de_Hilbert" title="Programme de Hilbert">programme de Hilbert</a>. De plus, pour prouver son premier théorème d’incomplétude, il utilise le <a href="/wiki/Codage_de_G%C3%B6del" title="Codage de Gödel">codage de Gödel</a> et un <a href="/wiki/Argument_de_la_diagonale_de_Cantor#Calculabilité" title="Argument de la diagonale de Cantor">argument diagonal</a> (découvert par <a href="/wiki/Georg_Cantor" title="Georg Cantor">Georg Cantor</a> en 1891) que la théorie de la calculabilité utilise beaucoup (notamment pour le <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>). </p><p>En 1933, Gödel part pour la première fois aux États-Unis. Il met au point l'idée de la calculabilité et étudie les <a href="/wiki/Algorithme_r%C3%A9cursif" title="Algorithme récursif">fonctions récursives</a>, si bien qu'il donne une conférence sur les fonctions récursives générales et le concept de vérité (voir : section Vérité et démontrabilité, <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>). Ces travaux sont développés en utilisant la construction de la <a href="/wiki/Codage_de_G%C3%B6del" title="Codage de Gödel">numérotation de Gödel</a>. </p><p><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> ainsi que <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo Church</a> montrent indépendamment l’indécidabilité du <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> de Hilbert<sup id="cite_ref-origine_2-2" class="reference"><a href="#cite_note-origine-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup> : </p> <ul><li>Church est connu pour le développement du <a href="/wiki/Lambda-calcul" title="Lambda-calcul">lambda-calcul</a> (premier formalisme définissant les <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a>, qui a une grande importance dans la théorie de la calculabilité) pour la première démonstration de l’indécidabilité du <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> (un problème de décision particulier).</li> <li>Turing, quant à lui, caractérise un peu plus tard en 1936, dans son article « <i>On Computable Numbers, with an Application to the Entscheidungsproblem</i> », ce qu’est un procédé calculable. Pour cela, il imagine non pas une machine matérielle, mais un « être calculant » qui peut être un appareil logique très simple ou un <a href="/wiki/Calculateur_humain" title="Calculateur humain">humain</a> bien discipliné appliquant des règles. On appellera cette machine, la <a href="/wiki/Machine_de_Turing" title="Machine de Turing">machine de Turing</a>. Dans le cours de son raisonnement, il démontre que le problème de l’arrêt d’une machine de Turing ne peut être résolu par algorithme : il n’est pas possible de décider avec un <a href="/wiki/Algorithme" title="Algorithme">algorithme</a> (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera. Son article présente également la notion de <a href="/wiki/Nombre_r%C3%A9el_calculable" title="Nombre réel calculable">nombre réel calculable</a> puisqu’il déduit de l'<a href="/wiki/D%C3%A9cidabilit%C3%A9" title="Décidabilité">indécidabilité</a> du problème de l'arrêt que l'on peut définir des <a href="/wiki/Nombre_r%C3%A9el" title="Nombre réel">nombres réels</a> qui ne sont pas calculables. Turing introduit ainsi les concepts de programme et de programmation.</li></ul> <p><a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Kleene</a> et Turing démontrent en 1938 que le <a href="/wiki/Lambda-calcul" title="Lambda-calcul">lambda-calcul</a> de Church, les <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions générales récursives</a> (modèle dit de Herbrand-<a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Gödel</a>) et les machines de Turing ont des capacités équivalentes. Cette équivalence démontre ensuite qu'un certain nombre de formalisations mathématiques de la notion de traitement par des processus mécaniques ont des aptitudes en tous points semblables à l'intuition de Church. Cette constatation aboutit à la <a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a> (appelée aussi <i>thèse de Church-Turing</i>)<sup id="cite_ref-origine_2-3" class="reference"><a href="#cite_note-origine-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Modèles_de_calcul"><span id="Mod.C3.A8les_de_calcul"></span>Modèles de calcul</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=7" title="Modifier la section : Modèles de calcul" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=7" title="Modifier le code source de la section : Modèles de calcul"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Plusieurs modèles de calcul sont utilisés en calculabilité : </p> <ul><li>les <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a> ;</li> <li>le <a href="/wiki/Lambda-calcul" title="Lambda-calcul">lambda-calcul</a> ;</li> <li>les <a href="/wiki/Machine_de_Turing" title="Machine de Turing">machines de Turing</a> ;</li> <li>les <a href="/wiki/Machine_%C3%A0_compteurs" title="Machine à compteurs">machines à compteurs</a> ;</li> <li>les <a href="/wiki/Automate_cellulaire" title="Automate cellulaire">automates cellulaires</a> ;</li> <li>les <a href="/wiki/Circuit_bool%C3%A9en" title="Circuit booléen">circuits booléens</a> ;</li> <li>les <a href="/wiki/Parallel_random_access_machine" title="Parallel random access machine">machines parallèle à accès arbitraire</a> ou <i>PRAM</i> ;</li> <li>les <a href="/wiki/Random_access_machine" title="Random access machine">Random access machines</a> ou <i>RAM</i> ;</li> <li>les <a href="/wiki/Machine_de_Blum-Shub-Smale" title="Machine de Blum-Shub-Smale">machines de Blum-Shub-Smale</a>.</li></ul> <p>Malgré la diversité de ces modèles, la classe de <a href="/wiki/Fonction_calculable" class="mw-redirect" title="Fonction calculable">fonctions calculables</a> par chacun de ceux-ci est unique et cette constatation est le fondement de la <a href="/wiki/Th%C3%A8se_de_Church" title="Thèse de Church">thèse de Church</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Organisations_professionnelles">Organisations professionnelles</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=8" title="Modifier la section : Organisations professionnelles" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=8" title="Modifier le code source de la section : Organisations professionnelles"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La principale organisation professionnelle pour la théorie de la récursivité est l'<i><a href="/wiki/Association_for_Symbolic_Logic" title="Association for Symbolic Logic">Association for Symbolic Logic</a></i> (<i>ASL</i>), qui publie de nombreux ouvrages académiques et revues universitaires. L'association <i><a href="/wiki/Computability_in_Europe" title="Computability in Europe">Computability in Europe</a></i> (<i>CiE</i>) organise une série de conférences annuelles. </p> <div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&veaction=edit&section=9" title="Modifier la section : Notes et références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&action=edit&section=9" title="Modifier le code source de la section : Notes et 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">Historiquement, la première caractérisation formelle et mathématique des algorithmes</span> </li> <li id="cite_note-origine-2"><span class="mw-cite-backlink noprint">↑ <sup><a href="#cite_ref-origine_2-0">a</a> <a href="#cite_ref-origine_2-1">b</a> <a href="#cite_ref-origine_2-2">c</a> et <a href="#cite_ref-origine_2-3">d</a></sup> </span><span class="reference-text"><i><span class="lang-en" lang="en">Origins of Recursive Function Theory</span></i> dans <i><span class="lang-en" lang="en">Annals of the History of Computing</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 3 <abbr class="abbr" title="Numéro">N<sup>o</sup></abbr> 1, janvier 1981.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink noprint"><a href="#cite_ref-3">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <span class="ouvrage" id="LewisPapadimitriou1998"><span class="ouvrage" id="Harry_R._LewisChristos_Papadimitriou1998"><a href="/w/index.php?title=Harry_R._Lewis&action=edit&redlink=1" class="new" title="Harry R. Lewis (page inexistante)">Harry R. Lewis</a> et <a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a>, <cite class="italique">Elements of the Theory of Computation</cite>, <a href="/wiki/Prentice-Hall" class="mw-redirect" title="Prentice-Hall">Prentice-Hall</a>, <time>1998</time> (<abbr class="abbr" title="première">1<sup>re</sup></abbr> <abbr class="abbr" title="édition">éd.</abbr> 1982)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elements+of+the+Theory+of+Computation&rft.pub=Prentice-Hall&rft.aulast=Lewis&rft.aufirst=Harry+R.&rft.au=Christos+Papadimitriou&rft.date=1998&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></span>.</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink noprint"><a href="#cite_ref-4">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-format format-pdf" title="Document au format Portable Document Format (PDF)">[PDF]</abbr> <a rel="nofollow" class="external text" href="http://www.fil.univ-lille1.fr/~wegrzyno/portail/API2/Doc/Cours/chap8.pdf"><i>Peut-on tout programmer ?</i> Cours de l'université de Lille</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="de_Solla_Price1974"><span class="ouvrage" id="Derek_de_Solla_Price1974">Derek de Solla Price, « <cite style="font-style:normal">Gears from the Greeks. The Antikythera Mechanism: A Calendar Computer from ca. 80 B. C.</cite> », <i>Transactions of the American Philosophical Society</i>, <abbr class="abbr" title="volume">vol.</abbr> 64, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 7,‎ <time>1974</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">1-70</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Gears+from+the+Greeks.+The+Antikythera+Mechanism%3A+A+Calendar+Computer+from+ca.+80+B.+C.&rft.jtitle=Transactions+of+the+American+Philosophical+Society&rft.issue=7&rft.au=Derek+de+Solla+Price&rft.date=1974&rft.volume=64&rft.pages=1-70&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></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="Freeth1999"><span class="ouvrage" id="Tony_Freeth1999">Tony Freeth, « <cite style="font-style:normal">L’horloge astronomique d'Anticythère</cite> », <i>Pour la Science</i>, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 389,‎ <time class="nowrap" datetime="1999-11-30" data-sort-value="1999-11-30">30 novembre 1999</time><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=L%E2%80%99horloge+astronomique+d%27Anticyth%C3%A8re&rft.jtitle=Pour+la+Science&rft.issue=389&rft.aulast=Freeth&rft.aufirst=Tony&rft.date=1999-11-30&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></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">« <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=-jOfPzezh44"><cite style="font-style:normal;">La machine d'Anticythère - Documentaire "Bâtisseurs de l'Ancien Monde"</cite></a> »</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">Voir <a href="/wiki/Calculatrice_m%C3%A9canique#Horloges_à_calculer_imparfaites" title="Calculatrice mécanique">Horloges_à_calculer_imparfaites</a>.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink noprint"><a href="#cite_ref-9">↑</a> </span><span class="reference-text">Voir <a href="/wiki/Calculatrice_m%C3%A9canique#Premières_machines_à_calculer" title="Calculatrice mécanique">Premières_machines_à_calculer</a>.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink noprint"><a href="#cite_ref-10">↑</a> </span><span class="reference-text">Youri Matiiassevitch, <i>Le dixième problème de Hilbert : son indécidabilité</i>, Masson, 1995 <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-22584835-3" title="Spécial:Ouvrages de référence/978-2-22584835-3"><span class="nowrap">978-2-22584835-3</span></a>)</small></span> </li> </ol></div> </div> <div class="mw-heading mw-heading2"><h2 id="Bibliographie">Bibliographie</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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> <ul><li><span class="ouvrage">« <a rel="nofollow" class="external text" href="http://www.labri.fr/perso/anca/MC/poly.pdf"><cite style="font-style:normal;">[PDF] Complexité et calculabilité, université de Bordeaux</cite></a> »</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="Carton2008"><span class="ouvrage" id="Olivier_Carton2008">Olivier <span class="nom_auteur">Carton</span>, <cite class="italique">Langages formels, calculabilité et complexité</cite>, <time>2008</time> <small>[<a href="/wiki/R%C3%A9f%C3%A9rence:Langages_formels,_calculabilit%C3%A9_et_complexit%C3%A9_(Carton)" title="Référence:Langages formels, calculabilité et complexité (Carton)">détail de l’édition</a>]</small> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.normalesup.org/~bisson/tea/lfcc.pdf">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=Langages+formels%2C+calculabilit%C3%A9+et+complexit%C3%A9&rft.aulast=Carton&rft.aufirst=Olivier&rft.date=2008&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></span></li> <li>Jean-Michel Autebert, <i>Calculabilité et décidabilité</i>, <a href="/wiki/Dunod" class="mw-redirect" title="Dunod">Dunod</a>, 1992 <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-2225826320" title="Spécial:Ouvrages de référence/978-2225826320"><span class="nowrap">978-2225826320</span></a>)</small></li> <li><a href="/wiki/Pierre_Wolper" title="Pierre Wolper">Pierre Wolper</a>, <i>Introduction à la calculabilité</i>, Dunod, 2006, <abbr class="abbr" title="Troisième">3<sup>e</sup></abbr> éd. <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-2100499816" title="Spécial:Ouvrages de référence/978-2100499816"><span class="nowrap">978-2100499816</span></a>)</small></li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/George_Boolos" title="George Boolos">George Boolos</a>, <a href="/wiki/John_P._Burgess" title="John P. Burgess">John P. Burgess</a> et <a href="/w/index.php?title=Richard_Jeffrey&action=edit&redlink=1" class="new" title="Richard Jeffrey (page inexistante)">Richard Jeffrey</a>, <i>Computability and Logic</i>, Cambridge, 2007, <abbr class="abbr" title="Cinquième">5<sup>e</sup></abbr> éd. <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-0521701464" title="Spécial:Ouvrages de référence/978-0521701464"><span class="nowrap">978-0521701464</span></a>)</small></li> <li><span class="ouvrage" id="Lacombe1960"><span class="ouvrage" id="Daniel_Lacombe1960">Daniel Lacombe, « <cite style="font-style:normal">La théorie des fonctions récursives et ses applications (Exposé d’information générale)</cite> », <i><a href="/wiki/Bulletin_de_la_Soci%C3%A9t%C3%A9_math%C3%A9matique_de_France" title="Bulletin de la Société mathématique de France">Bulletin de la Société mathématique de France</a></i>, <abbr class="abbr" title="volume">vol.</abbr> 88,‎ <time>1960</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">393-468</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.numdam.org/article/BSMF_1960__88__393_0.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=La+th%C3%A9orie+des+fonctions+r%C3%A9cursives+et+ses+applications+%28Expos%C3%A9+d%E2%80%99information+g%C3%A9n%C3%A9rale%29&rft.jtitle=Bulletin+de+la+Soci%C3%A9t%C3%A9+math%C3%A9matique+de+France&rft.aulast=Lacombe&rft.aufirst=Daniel&rft.date=1960&rft.volume=88&rft.pages=393-468&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></span></li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a>, « On Computable Numbers, with an Application to the Entscheidungsproblem », <i>Proceedings of the London Mathematical Society</i>, <a href="/wiki/London_Mathematical_Society" title="London Mathematical Society">London Mathematical Society</a>, 1937</li> <li><span class="ouvrage" id="Barry_Cooper2004"><span class="ouvrage" id="S._Barry_Cooper2004"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/S._Barry_Cooper" title="S. Barry Cooper">S. Barry Cooper</a>, <cite class="italique" lang="en">Computability Theory</cite>, Chapman & Hall / CRC, <time>2004</time> <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/1-58488-237-9" title="Spécial:Ouvrages de référence/1-58488-237-9"><span class="nowrap">1-58488-237-9</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=Computability+Theory&rft.pub=Chapman+%26+Hall+%2F+CRC&rft.au=S.+Barry+Cooper&rft.date=2004&rft.isbn=1-58488-237-9&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></span>.</li> <li><span class="ouvrage" id="MoninPatey2022"><span class="ouvrage" id="Benoît_MoninLudovic_Patey2022">Benoît Monin et Ludovic Patey, <cite class="italique">Calculabilité</cite>, Calvage et Mounet, <time class="nowrap" datetime="2022-04" data-sort-value="2022-04">avril 2022</time>, 828 <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-916352-96-1" title="Spécial:Ouvrages de référence/978-2-916352-96-1"><span class="nowrap">978-2-916352-96-1</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=Calculabilit%C3%A9&rft.pub=Calvage+et+Mounet&rft.aulast=Monin&rft.aufirst=Beno%C3%AEt&rft.au=Ludovic+Patey&rft.date=2022-04&rft.tpages=828&rft.isbn=978-2-916352-96-1&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></span>. — Ouvrage très complet qui aborde des sujets avancés comme la <a href="/wiki/Suite_al%C3%A9atoire" title="Suite aléatoire">la théorie algorithmique de l'aléatoire</a>, les <a href="/wiki/Math%C3%A9matiques_%C3%A0_rebours" title="Mathématiques à rebours">mathématiques à rebours</a> et l'<a href="/wiki/Hypercalcul" title="Hypercalcul">hypercalculabilité</a>.</li> <li>Michel Bourdeau et Jean Mosconi, <i>Anthologie de la calculabilité</i>, recueil de textes, édition Cassini, ouvrage en attente de publication depuis décembre 2020.</li> <li><span class="ouvrage" id="Cori-Lascar_II"><a href="/wiki/Ren%C3%A9_Cori" title="René Cori">René <span class="nom_auteur">Cori</span></a> et Daniel <span class="nom_auteur">Lascar</span>, <cite class="italique">Logique <span class="nowrap">mathématique <abbr class="abbr" title="2"><span class="romain" style="text-transform:uppercase">II</span></abbr></span>. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles</cite> <small>[<a href="/wiki/R%C3%A9f%C3%A9rence:Logique_math%C3%A9matique_2_(Cori-Lascar)" title="Référence:Logique mathématique 2 (Cori-Lascar)">détail des éditions</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=Logique+math%C3%A9matique+II.+Fonctions+r%C3%A9cursives%2C+th%C3%A9or%C3%A8me+de+G%C3%B6del%2C+th%C3%A9orie+des+ensembles%2C+th%C3%A9orie+des+mod%C3%A8les&rft.aulast=Cori&rft.aufirst=Ren%C3%A9&rft.au=Lascar%2C+Daniel&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A9orie+de+la+calculabilit%C3%A9"></span></span></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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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="wiktionary"><a href="https://fr.wiktionary.org/wiki/calculabilit%C3%A9" class="extiw" title="wikt:calculabilité">calculabilité</a>, <span class="nowrap">sur le <span class="project">Wiktionnaire</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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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> <div style="column-width:19em;column-count:3;margin:.3em 0;" class="colonnes"><div style="margin:-.3em 0;"> <ul><li><a href="/wiki/Suite_d%27entiers" title="Suite d'entiers">Suite d'entiers</a></li> <li><a href="/wiki/Th%C3%A9or%C3%A8me_de_r%C3%A9cursion_de_Kleene" title="Théorème de récursion de Kleene">Théorème de récursion de Kleene</a></li> <li><a href="/wiki/Hi%C3%A9rarchie_arithm%C3%A9tique" title="Hiérarchie arithmétique">Hiérarchie arithmétique</a></li> <li><a href="/wiki/Nombre_r%C3%A9el_calculable" title="Nombre réel calculable">Nombre réel calculable</a></li> <li><a href="/wiki/Computationnalisme" title="Computationnalisme">Computationnalisme</a></li> <li><a href="/wiki/Th%C3%A9or%C3%A8me_de_Rice" title="Théorème de Rice">Théorème de Rice</a></li> <li><a href="/wiki/Om%C3%A9ga_de_Chaitin" title="Oméga de Chaitin">Oméga de Chaitin</a></li></ul> </div></div> <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 class="mw-selflink selflink">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 href="/wiki/Machine_de_Turing" title="Machine de Turing">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> <li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Logique" title="Portail de la logique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/48px-Logic.svg.png" decoding="async" width="48" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/72px-Logic.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Logic.svg/96px-Logic.svg.png 2x" data-file-width="85" data-file-height="28" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Logique" title="Portail:Logique">Portail de la logique</a></span> </span></li> <li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Math%C3%A9matiques" title="Portail des mathématiques"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/24px-Racine_carr%C3%A9e_bleue.svg.png" decoding="async" width="24" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/36px-Racine_carr%C3%A9e_bleue.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/48px-Racine_carr%C3%A9e_bleue.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Math%C3%A9matiques" title="Portail:Mathématiques">Portail des mathématiques</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" 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=Théorie_de_la_calculabilité&oldid=216878144">https://fr.wikipedia.org/w/index.php?title=Théorie_de_la_calculabilité&oldid=216878144</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:Calculabilit%C3%A9" title="Catégorie:Calculabilité">Calculabilité</a></li><li><a href="/wiki/Cat%C3%A9gorie:Logique_math%C3%A9matique" title="Catégorie:Logique mathématique">Logique mathématique</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_%C3%A0_r%C3%A9f%C3%A9rence_n%C3%A9cessaire" title="Catégorie:Article à référence nécessaire">Article à référence nécessaire</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><li><a href="/wiki/Cat%C3%A9gorie:Portail:Logique/Articles_li%C3%A9s" title="Catégorie:Portail:Logique/Articles liés">Portail:Logique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Sciences/Articles_li%C3%A9s" title="Catégorie:Portail:Sciences/Articles liés">Portail:Sciences/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Math%C3%A9matiques/Articles_li%C3%A9s" title="Catégorie:Portail:Mathématiques/Articles liés">Portail:Mathématiques/Articles liés</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 17 juillet 2024 à 14:23.</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/Th%C3%A9orie_de_la_calculabilit%C3%A9" title="Spécial:Citer/Théorie de la calculabilité">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=Th%C3%A9orie_de_la_calculabilit%C3%A9&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-65496f48b4-b9g42","wgBackendResponseTime":178,"wgPageParseReport":{"limitreport":{"cputime":"0.237","walltime":"0.346","ppvisitednodes":{"value":2707,"limit":1000000},"postexpandincludesize":{"value":68983,"limit":2097152},"templateargumentsize":{"value":11889,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":0,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":9273,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 234.514 1 -total"," 22.96% 53.841 1 Modèle:Références"," 16.77% 39.319 1 Modèle:Portail"," 14.77% 34.642 5 Modèle:Ouvrage"," 9.07% 21.271 2 Modèle:Lang"," 8.62% 20.222 1 Modèle:Autres_projets"," 8.42% 19.748 1 Modèle:Suivi_des_biographies"," 7.54% 17.692 2 Modèle:Citation"," 6.48% 15.197 1 Modèle:Palette"," 6.19% 14.522 1 Modèle:-s-"]},"scribunto":{"limitreport-timeusage":{"value":"0.066","limit":"10.000"},"limitreport-memusage":{"value":4438869,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-bxzm6","timestamp":"20241124201806","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Th\u00e9orie de la calculabilit\u00e9","url":"https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9orie_de_la_calculabilit%C3%A9","sameAs":"http:\/\/www.wikidata.org\/entity\/Q818930","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q818930","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-04-23T15:58:10Z","dateModified":"2024-07-17T13:23:54Z","headline":"domaine de la logique math\u00e9matique et de l\u2019informatique th\u00e9orique \u00e9tudiant les fonctions calculables et les degr\u00e9s Turing"}</script> </body> </html>