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èse de Church — 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":"2f882ccf-ce04-45da-868e-50aae79b5eba","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Thèse_de_Church","wgTitle":"Thèse de Church","wgCurRevisionId":220522668,"wgRevisionId":220522668,"wgArticleId":59972,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article contenant un appel à traduction en anglais","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Intelligence artificielle","Calculabilité","Alan Turing"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName":"Thèse_de_Church","wgRelevantArticleId":59972,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true, "wgRestrictionEdit":[],"wgRestrictionMove":[],"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":30000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q309157","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.cite.styles":"ready","ext.math.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=["ext.cite.ux-enhancements","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.gadget.Wdsearch","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface", "ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Thèse de Church — 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%A8se_de_Church"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Th%C3%A8se_de_Church&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%A8se_de_Church"> <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èse_de_Church rootpage-Thèse_de_Church 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%A8se+de+Church" 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%A8se+de+Church" 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%A8se+de+Church" 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%A8se+de+Church" 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-Formulation_de_la_thèse" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formulation_de_la_thèse"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Formulation de la thèse</span> </div> </a> <button aria-controls="toc-Formulation_de_la_thèse-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 Formulation de la thèse</span> </button> <ul id="toc-Formulation_de_la_thèse-sublist" class="vector-toc-list"> <li id="toc-Qu'est-ce_qu'une_thèse_?" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Qu'est-ce_qu'une_thèse_?"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Qu'est-ce qu'une thèse ?</span> </div> </a> <ul id="toc-Qu'est-ce_qu'une_thèse_?-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Les_différentes_formulations_de_la_thèse_de_Church" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Les_différentes_formulations_de_la_thèse_de_Church"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Les différentes formulations de la thèse de Church</span> </div> </a> <ul id="toc-Les_différentes_formulations_de_la_thèse_de_Church-sublist" class="vector-toc-list"> </ul> </li> </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">2</span> <span>Histoire</span> </div> </a> <ul id="toc-Histoire-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Des_fonctions_et_nombres_non_calculables" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Des_fonctions_et_nombres_non_calculables"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Des fonctions et nombres non calculables</span> </div> </a> <ul id="toc-Des_fonctions_et_nombres_non_calculables-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Autres_modèles_de_calcul" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Autres_modèles_de_calcul"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Autres modèles de calcul</span> </div> </a> <ul id="toc-Autres_modèles_de_calcul-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Thèse_de_Church_et_calcul_quantique" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Thèse_de_Church_et_calcul_quantique"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Thèse de Church et calcul quantique</span> </div> </a> <ul id="toc-Thèse_de_Church_et_calcul_quantique-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">6</span> <span>Notes et références</span> </div> </a> <button aria-controls="toc-Notes_et_références-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 Notes et références</span> </button> <ul id="toc-Notes_et_références-sublist" class="vector-toc-list"> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Références" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Références"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Références</span> </div> </a> <ul id="toc-Références-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Voir_aussi" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voir_aussi"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Voir aussi</span> </div> </a> <button aria-controls="toc-Voir_aussi-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Voir aussi</span> </button> <ul id="toc-Voir_aussi-sublist" class="vector-toc-list"> <li id="toc-Articles_connexes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Articles_connexes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.1</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sources" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sources"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2</span> <span>Sources</span> </div> </a> <ul id="toc-Sources-sublist" class="vector-toc-list"> <li id="toc-Articles_originaux" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Articles_originaux"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2.1</span> <span>Articles originaux</span> </div> </a> <ul id="toc-Articles_originaux-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Autres_(en_anglais)" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Autres_(en_anglais)"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2.2</span> <span>Autres (en anglais)</span> </div> </a> <ul id="toc-Autres_(en_anglais)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Autres_(en_français)" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Autres_(en_français)"> <div class="vector-toc-text"> <span class="vector-toc-numb">7.2.3</span> <span>Autres (en français)</span> </div> </a> <ul id="toc-Autres_(en_français)-sublist" class="vector-toc-list"> </ul> </li> </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èse de Church</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 36 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-36" 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">36 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/%D8%A3%D8%B7%D8%B1%D9%88%D8%AD%D8%A9_%D8%AA%D8%B4%D8%B1%D8%B4-%D8%AA%D9%88%D8%B1%D9%8A%D9%86%D8%BA" title="أطروحة تشرش-تورينغ – arabe" lang="ar" hreflang="ar" data-title="أطروحة تشرش-تورينغ" data-language-autonym="العربية" data-language-local-name="arabe" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%BD%D0%B0_%D0%A7%D1%8A%D1%80%D1%87" 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-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Tesi_de_Church-Turing" title="Tesi de Church-Turing – catalan" lang="ca" hreflang="ca" data-title="Tesi de Church-Turing" 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/Churchova%E2%80%93Turingova_teze" title="Churchova–Turingova teze – tchèque" lang="cs" hreflang="cs" data-title="Churchova–Turingova teze" data-language-autonym="Čeština" data-language-local-name="tchèque" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Church-Turing-tesen" title="Church-Turing-tesen – danois" lang="da" hreflang="da" data-title="Church-Turing-tesen" 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/Church-Turing-These" title="Church-Turing-These – allemand" lang="de" hreflang="de" data-title="Church-Turing-These" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis" title="Church–Turing thesis – anglais" lang="en" hreflang="en" data-title="Church–Turing thesis" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/%C4%88ur%C4%89a_tezo" title="Ĉurĉa tezo – espéranto" lang="eo" hreflang="eo" data-title="Ĉurĉa tezo" data-language-autonym="Esperanto" data-language-local-name="espéranto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Tesis_de_Church-Turing" title="Tesis de Church-Turing – espagnol" lang="es" hreflang="es" data-title="Tesis de Church-Turing" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Churchi_tees" title="Churchi tees – estonien" lang="et" hreflang="et" data-title="Churchi tees" data-language-autonym="Eesti" data-language-local-name="estonien" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%B2_%DA%86%D8%B1%DA%86-%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF" title="تز چرچ-تورینگ – persan" lang="fa" hreflang="fa" data-title="تز چرچ-تورینگ" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Churchin%E2%80%93Turingin_teesi" title="Churchin–Turingin teesi – finnois" lang="fi" hreflang="fi" data-title="Churchin–Turingin teesi" data-language-autonym="Suomi" data-language-local-name="finnois" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%AA%D7%96%D7%AA_%D7%A6%27%D7%A8%D7%A5%27-%D7%98%D7%99%D7%95%D7%A8%D7%99%D7%A0%D7%92" title="תזת צ'רץ'-טיורינג – hébreu" lang="he" hreflang="he" data-title="תזת צ'רץ'-טיורינג" data-language-autonym="עברית" data-language-local-name="hébreu" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Church-Turingova_teza" title="Church-Turingova teza – croate" lang="hr" hreflang="hr" data-title="Church-Turingova teza" data-language-autonym="Hrvatski" data-language-local-name="croate" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-hu mw-list-item"><a href="https://hu.wikipedia.org/wiki/Church%E2%80%93Turing-t%C3%A9zis" title="Church–Turing-tézis – hongrois" lang="hu" hreflang="hu" data-title="Church–Turing-tézis" data-language-autonym="Magyar" data-language-local-name="hongrois" class="interlanguage-link-target"><span>Magyar</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Tesis_Church_Turing" title="Tesis Church Turing – indonésien" lang="id" hreflang="id" data-title="Tesis Church Turing" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonésien" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Tesi_di_Church-Turing" title="Tesi di Church-Turing – italien" lang="it" hreflang="it" data-title="Tesi di Church-Turing" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A3%E3%83%BC%E3%83%81%EF%BC%9D%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E3%83%86%E3%83%BC%E3%82%BC" 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/%EC%B2%98%EC%B9%98-%ED%8A%9C%EB%A7%81_%EB%85%BC%EC%A0%9C" 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-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Tiuringo_ma%C5%A1ina#Tiuringo_tezė" title="Tiuringo mašina – lituanien" lang="lt" hreflang="lt" data-title="Tiuringo mašina" data-language-autonym="Lietuvių" data-language-local-name="lituanien" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%9A%E0%B5%BC%E0%B4%9A%E0%B5%8D%E0%B4%9A%E0%B5%8D-%E0%B4%9F%E0%B5%8D%E0%B4%AF%E0%B5%82%E0%B4%B1%E0%B4%BF%E0%B4%99%E0%B5%8D%E0%B4%99%E0%B5%8D_%E0%B4%B8%E0%B4%BF%E0%B4%A6%E0%B5%8D%E0%B4%A7%E0%B4%BE%E0%B4%A8%E0%B5%8D%E0%B4%A4%E0%B4%82" title="ചർച്ച്-ട്യൂറിങ്ങ് സിദ്ധാന്തം – malayalam" lang="ml" hreflang="ml" data-title="ചർച്ച്-ട്യൂറിങ്ങ് സിദ്ധാന്തം" data-language-autonym="മലയാളം" data-language-local-name="malayalam" class="interlanguage-link-target"><span>മലയാളം</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Church-Turing-hypothese" title="Church-Turing-hypothese – néerlandais" lang="nl" hreflang="nl" data-title="Church-Turing-hypothese" data-language-autonym="Nederlands" data-language-local-name="néerlandais" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Hipoteza_Churcha-Turinga" title="Hipoteza Churcha-Turinga – polonais" lang="pl" hreflang="pl" data-title="Hipoteza Churcha-Turinga" data-language-autonym="Polski" data-language-local-name="polonais" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pms mw-list-item"><a href="https://pms.wikipedia.org/wiki/Tesi_%C3%ABd_Church" title="Tesi ëd Church – piémontais" lang="pms" hreflang="pms" data-title="Tesi ëd Church" data-language-autonym="Piemontèis" data-language-local-name="piémontais" class="interlanguage-link-target"><span>Piemontèis</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Tese_de_Church-Turing" title="Tese de Church-Turing – portugais" lang="pt" hreflang="pt" data-title="Tese de Church-Turing" data-language-autonym="Português" data-language-local-name="portugais" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Teza_Church-Turing" title="Teza Church-Turing – roumain" lang="ro" hreflang="ro" data-title="Teza Church-Turing" data-language-autonym="Română" data-language-local-name="roumain" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D1%91%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0" title="Тезис Чёрча — Тьюринга – russe" lang="ru" hreflang="ru" data-title="Тезис Чёрча — Тьюринга" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Church-Turingova_teza" title="Church-Turingova teza – serbo-croate" lang="sh" hreflang="sh" data-title="Church-Turingova teza" 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/Church%E2%80%93Turing_thesis" title="Church–Turing thesis – Simple English" lang="en-simple" hreflang="en-simple" data-title="Church–Turing thesis" 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-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A7%D0%B5%D1%80%D1%87-%D0%A2%D1%98%D1%83%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D0%B0_%D1%82%D0%B5%D0%B7%D0%B0" title="Черч-Тјурингова теза – serbe" lang="sr" hreflang="sr" data-title="Черч-Тјурингова теза" data-language-autonym="Српски / srpski" data-language-local-name="serbe" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Church-Turings_hypotes" title="Church-Turings hypotes – suédois" lang="sv" hreflang="sv" data-title="Church-Turings hypotes" data-language-autonym="Svenska" data-language-local-name="suédois" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Tesis_na_Church-Turing" title="Tesis na Church-Turing – tagalog" lang="tl" hreflang="tl" data-title="Tesis na Church-Turing" data-language-autonym="Tagalog" data-language-local-name="tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Church-Turing_tezi" title="Church-Turing tezi – turc" lang="tr" hreflang="tr" data-title="Church-Turing tezi" 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%B7%D0%B0_%D0%A7%D0%B5%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8E%D1%80%D1%96%D0%BD%D0%B3%D0%B0" title="Теза Черча — Тюрінга – ukrainien" lang="uk" hreflang="uk" data-title="Теза Черча — Тюрінга" data-language-autonym="Українська" data-language-local-name="ukrainien" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E9%82%B1%E5%A5%87-%E5%9B%BE%E7%81%B5%E8%AE%BA%E9%A2%98" 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%9C%96%E9%9D%88%E8%AB%96%E9%A1%8C" 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/Q309157#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%A8se_de_Church" 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%A8se_de_Church" 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%A8se_de_Church"><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%A8se_de_Church&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%A8se_de_Church&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%A8se_de_Church&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%A8se_de_Church"><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%A8se_de_Church&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%A8se_de_Church&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%A8se_de_Church&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%A8se_de_Church" 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%A8se_de_Church" 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%A8se_de_Church&oldid=220522668" 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%A8se_de_Church&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%A8se_de_Church&id=220522668&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%25A8se_de_Church"><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%25A8se_de_Church"><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%A8se+de+Church"><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%A8se_de_Church&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%A8se_de_Church&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:Turing_machines" 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/Q309157" 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"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><div class="bandeau-container metadata homonymie hatnote"><div class="bandeau-cell bandeau-icone" style="display:table-cell;padding-right:0.5em"><span class="noviewer" typeof="mw:File"><a href="/wiki/Aide:Homonymie" title="Aide:Homonymie"><img alt="Page d’aide sur l’homonymie" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png" decoding="async" width="20" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/30px-Logo_disambig.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/40px-Logo_disambig.svg.png 2x" data-file-width="512" data-file-height="375" /></a></span></div><div class="bandeau-cell" style="display:table-cell;padding-right:0.5em"> <p>Pour l’article homonyme, voir <a href="/wiki/Th%C3%A8se_de_Church_(math%C3%A9matiques_constructives)" title="Thèse de Church (mathématiques constructives)">Thèse de Church (mathématiques constructives)</a>. </p> </div></div> <p>La <b>thèse de Church</b> — du nom du mathématicien <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo Church</a> — est une <a href="/wiki/Th%C3%A8se" title="Thèse">thèse</a> concernant la définition de la notion de <a href="/wiki/Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">calculabilité</a>. </p><p>Dans une forme dite « physique »<sup id="cite_ref-Dowek_1-0" class="reference"><a href="#cite_note-Dowek-1"><span class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup>, elle affirme que la notion physique de la calculabilité, définie comme étant tout traitement systématique réalisable par un processus physique ou mécanique, peut être exprimée par un ensemble de règles de calcul, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes. </p><p>Dans sa forme dite « psychologique »<sup id="cite_ref-Dowek_1-1" class="reference"><a href="#cite_note-Dowek-1"><span class="cite_crochet">[</span>1<span class="cite_crochet">]</span></a></sup>, elle affirme que la notion intuitive de calculabilité, qui est liée à ce qu'un être humain considère comme effectivement calculable ou non, peut également être exprimée par ces mêmes ensembles de règles de calcul formelles. </p><p><a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Kleene</a> fut le premier à nommer « thèse de Church » (en 1943 et 1952) ce que ce dernier présentait comme une définition de la calculabilité effective. Elle est également connue sous le nom plus récent de <b>thèse de Church-Turing</b>, terminologie proposée par certains spécialistes<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite_crochet">[</span>2<span class="cite_crochet">]</span></a></sup> dans les années 1990. Bien que Church soit sans nul doute le premier, au début des années 1930, à avoir pensé pouvoir définir formellement la calculabilité intuitive (par la <a href="/wiki/Lambda-calcul" title="Lambda-calcul">λ-définissabilité</a>)<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>, ce sont cependant l'article d'<a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> de 1936 et son modèle mécanique de calculabilité qui ont définitivement emporté l'adhésion, selon <a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Gödel</a>, Kleene et Church lui-même. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Formulation_de_la_thèse"><span id="Formulation_de_la_th.C3.A8se"></span>Formulation de la thèse</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=1" title="Modifier la section : Formulation de la thèse" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=1" title="Modifier le code source de la section : Formulation de la thèse"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La thèse est formulée en disant que des règles formelles de calcul (<a href="/wiki/Machine_de_Turing" title="Machine de Turing">machines de Turing</a>, les <a href="/wiki/Lambda_calcul" class="mw-redirect" title="Lambda calcul">fonctions λ-définissables</a>, les <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a>…) formalisent correctement la notion de <i>méthode effective de calcul</i>, ou de <a href="/wiki/Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">calculabilité</a><sup id="cite_ref-Vollat_4-0" class="reference"><a href="#cite_note-Vollat-4"><span class="cite_crochet">[</span>4<span class="cite_crochet">]</span></a></sup>. </p><p>On considère généralement<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> que la notion intuitive de méthode effective de calcul correspond aux caractéristiques suivantes : </p> <ol><li>l'algorithme consiste en un <a href="/wiki/Ensemble_fini" title="Ensemble fini">ensemble fini</a> d'instructions simples et précises qui sont décrites avec un nombre limité de symboles ;</li> <li>l'algorithme doit toujours produire le résultat en un nombre fini d'étapes ;</li> <li>l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon ;</li> <li>l'exécution de l'algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est nécessaire pour comprendre et exécuter les instructions.</li></ol> <p>Un exemple d'une telle méthode est l'<a href="/wiki/Algorithme_d%27Euclide" title="Algorithme d'Euclide">algorithme d'Euclide</a> pour déterminer le <a href="/wiki/Plus_grand_commun_diviseur" title="Plus grand commun diviseur">plus grand commun diviseur</a> d'entiers naturels ou celui qui détermine pour un entier <i>n</i> la longueur de la <a href="/wiki/Th%C3%A9or%C3%A8me_de_Goodstein" title="Théorème de Goodstein">suite de Goodstein</a> qui commence en <i>n</i>. </p> <div class="mw-heading mw-heading3"><h3 id="Qu'est-ce_qu'une_thèse_?"><span id="Qu.27est-ce_qu.27une_th.C3.A8se_.3F"></span>Qu'est-ce qu'une thèse ?</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=2" title="Modifier la section : Qu'est-ce qu'une thèse ?" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=2" title="Modifier le code source de la section : Qu'est-ce qu'une thèse ?"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Une <i>thèse</i> consiste à affirmer, sans le démontrer, qu'une notion intuitive correspond exactement à une notion formelle. Toute démonstration est impossible, il est seulement possible de la falsifier ou d'apporter des arguments en faveur ou en défaveur<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite_crochet">[</span>De 1<span class="cite_crochet">]</span></a></sup>. Un autre exemple de thèse consiste à affirmer que la notion intuitive de <a href="/wiki/Suite_al%C3%A9atoire" title="Suite aléatoire">suite de nombres tirés au hasard</a> correspond aux définitions formelles données par <a href="/wiki/Gregory_Chaitin" title="Gregory Chaitin">Gregory Chaitin</a> ou <a href="/wiki/Per_Martin-L%C3%B6f" title="Per Martin-Löf">Per Martin-Löf</a><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite_crochet">[</span>De 2<span class="cite_crochet">]</span></a></sup>. Les caractéristiques intuitives ne sont pas une formalisation en soi, car elle contient des termes informels comme « instruction simple et précise », ou « intelligence requise pour exécuter les instructions ». On peut en revanche <i>définir</i> formellement ce qu'est un algorithme et pour cela on a le choix entre les diverses règles formelles de calcul citées au début de ce paragraphe. À ce stade, la thèse de Church affirme que les deux notions, intuitive de « méthode effective », et formelle (« règles de calcul », ou « algorithme »), concordent, apportant ainsi une définition rigoureuse du concept de calculabilité. </p><p>En effet, au début du <a href="/wiki/XXe_si%C3%A8cle" title="XXe siècle"><abbr class="abbr" title="20ᵉ siècle"><span class="romain">XX</span><sup style="font-size:72%">e</sup></abbr> siècle</a>, les mathématiciens utilisaient des expressions informelles comme <i>effectivement réalisables</i>. Il était donc important de trouver une formalisation rigoureuse de ce concept. Depuis les années 1940, les mathématiciens utilisent grâce à la thèse de Church une notion bien définie, celle de <a href="/wiki/Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">fonction calculable</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Les_différentes_formulations_de_la_thèse_de_Church"><span id="Les_diff.C3.A9rentes_formulations_de_la_th.C3.A8se_de_Church"></span>Les différentes formulations de la thèse de Church</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=3" title="Modifier la section : Les différentes formulations de la thèse de Church" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=3" title="Modifier le code source de la section : Les différentes formulations de la thèse de Church"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>La thèse a d'abord été formulée pour le <a href="/wiki/Lambda-calcul" title="Lambda-calcul">lambda-calcul</a>, mais d'autres formalismes ont été proposés pour modéliser les fonctions calculables, par exemple les <a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">fonctions récursives</a>, les machines de Turing, les machines de <a href="/wiki/Emil_Post" title="Emil Post">Post</a> et les <a href="/wiki/Machine_%C3%A0_compteurs" title="Machine à compteurs">machines à compteurs</a>. La plus surprenante est probablement celle proposée par <a href="/wiki/Yuri_Matiyasevich" class="mw-redirect" title="Yuri Matiyasevich">Yuri Matiyasevich</a> en résolvant 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>. On peut montrer que toutes ces définitions, bien que fondées sur des idées assez différentes, décrivent exactement le même ensemble de fonctions. Ces systèmes, qui ont le même pouvoir d'expression que l'une quelconque de ces définitions équivalentes, sont dits <i>Turing-équivalents</i> ou <i><a href="/wiki/Turing-complet" title="Turing-complet">Turing-complets</a></i>. </p><p>Le fait que toutes ces tentatives pour formaliser le concept d'algorithme aient conduit à des résultats équivalents est un argument fort pour la thèse de Church. </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%A8se_de_Church&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%A8se_de_Church&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>La thèse de Church est énoncée clairement par Church dans le résumé de la conférence qu'il a donnée à l'<a href="/wiki/American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a> en 1935<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite_crochet">[</span>6<span class="cite_crochet">]</span></a></sup> : </p> <blockquote> <p>« ... Gödel a proposé ... une définition du terme <i>fonction récursive</i> dans un sens très général. Dans cet article un sens de <i>fonction récursive très générale sur les entiers positifs</i>, qui est essentiellement celui de Gödel, est adopté. Et il est affirmé que la notion de fonction effectivement calculable sur les entiers positifs devrait être identifiée avec celle de fonction générale récursive puisque toutes les autres notions de calculabilité effective se réduisent à des notions qui sont ou bien équivalentes ou bien plus faibles que la récursivité. » </p> </blockquote> <p>Dans son article de 1936 Church écrit<sup id="cite_ref-Church36_9-0" class="reference"><a href="#cite_note-Church36-9"><span class="cite_crochet">[</span>7<span class="cite_crochet">]</span></a></sup><sup class="reference cite_virgule">,</sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite_crochet">[</span>8<span class="cite_crochet">]</span></a></sup> : </p> <blockquote> <p>« Le fait cependant que deux définitions largement différentes et (du point de vue de l'auteur) tout aussi naturelles de la calculabilité effective se révèlent être équivalentes ajoutent de la force aux raisons invoquées ci-dessous de croire qu'elles constituent une caractérisation aussi bien générale que cohérente de sa compréhension intuitive habituelle. » </p> </blockquote> <p>Dans son article de 1943 <i>Prédicats et quantificateurs récursifs</i> (titre original <span class="lang-en" lang="en"><i>Recursive Predicates and Quantifiers</i></span>) <a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Kleene</a> (repris dans <i>L'Indécidable</i>, titre original <span class="lang-en" lang="en"><i>The Undecidable</i></span>) a utilisé le premier la terminologie « thèse » et l'a attribué à Church : </p> <blockquote> <p>« Ce fait heuristique [les fonctions récursives générales sont effectivement calculables]… a conduit Church à énoncer la thèse suivante » </p> </blockquote><p style="margin:-0.7em 0 0.3em 6em">— [note 22 de Kleene], <cite>La même thèse est implicite dans la description des machines de Turing [note 23 de Kleene].</cite></p> <blockquote> <p>« <i>THÈSE I. Chaque fonction effectivement calculable (chaque prédicat effectivement décidable) est récursive générale</i> [les italiques sont de Kleene] » </p> </blockquote> <blockquote> <p>« Puisque nous recherchions une définition mathématique précise de l'expression effectivement calculable (effectivement décidable), nous prendrons cette thèse comme sa définition […] » </p> </blockquote><p style="margin:-0.7em 0 0.3em 6em">— Kleene, <cite>dans <i>l'indécidable</i>, <abbr class="abbr" title="page(s)">p.</abbr> 274</cite></p> <p>La note 22 de Kleene fait référence à l'article de Church tandis que sa note 23 fait référence à l'article d'Alan Turing. Il continue en notant que </p> <blockquote> <p>« … la thèse n'est qu'une hypothèse -- une constatation déjà soulignée par <a href="/wiki/Emil_Post" title="Emil Post">Post</a> et par Church » </p> </blockquote><p style="margin:-0.7em 0 0.3em 6em">— [sa note 24, dans <i>L'indécidable</i>, P. 274], <cite>Il fait référence à l'article de Post (1936) et aux définitions formelles de l'article de Church <span class="lang-en" lang="en"><i>Formal definitions in the theory of ordinal numbers, Fund. Math.</i></span> vol. 28 (1936) pp.11-21 (voir réf. 2, P. 286, de <i>l'indécidable</i>).</cite></p> <p>Dans son article de 1936 <span class="citation">« sur des nombres calculables, avec une application à l'<a href="/wiki/Entscheidungsproblem" class="mw-redirect" title="Entscheidungsproblem">Entscheidungsproblem</a> »</span> (titre original <span class="citation">« <span class="lang-en" lang="en"><i>On Computable Numbers, with an Application to the Entscheidungsproblem</i></span> »</span>) Turing a formalisé la notion d'algorithme (alors appelée « calculabilité effective »), en introduisant les machines dites maintenant de Turing. Dans cet article il écrit en particulier à la page 239 : </p> <blockquote> <p>« Une suite calculable γ est déterminée par une description d'une machine qui calcule γ […] et, en fait, n'importe quelle suite calculable est susceptible d'être décrite en termes d'une table [c'est-à-dire d'une machine de Turing]. » </p> </blockquote> <p>Ce qui est la version de Turing de la thèse de Church, qu'il ne connaissait pas à l'époque. </p><p>Church avait démontré lui aussi quelques mois plus tôt l'insolvabilité du problème de la décision dans « une note sur l'Entscheidungsproblem »<sup id="cite_ref-Church36_9-1" class="reference"><a href="#cite_note-Church36-9"><span class="cite_crochet">[</span>7<span class="cite_crochet">]</span></a></sup> pour cela il avait utilisé les fonctions récursives et les fonctions λ-définissables pour décrire formellement la calculabilité effective. Les fonctions <i>λ-définissables</i> avait été introduites par Alonzo Church et Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935) et les fonctions récursives avaient été introduites par <a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a> et <a href="/wiki/Jacques_Herbrand" title="Jacques Herbrand">Jacques Herbrand</a> (Gödel 1934, Herbrand 1932). Ces deux formalismes décrivent le même ensemble de fonctions, comme cela a été démontré dans le cas des fonctions sur les entiers positifs par Church et Kleene (Church 1936a, Kleene 1936). Après avoir entendu parler de la proposition de Church, Turing a pu rapidement esquisser une démonstration que ses machines de Turing décrivent en fait le même ensemble de fonctions (Turing 1936, 263 <i>et suivantes</i>). Dans un article paru en 1937<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite_crochet">[</span>λdef 1<span class="cite_crochet">]</span></a></sup> il montre l'équivalence des trois modèles : fonctions λ-définissables, machines de Turing<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite_crochet">[</span>9<span class="cite_crochet">]</span></a></sup> et fonctions générales récursives au sens de Herbrand et Gödel. Rosser<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite_crochet">[</span>10<span class="cite_crochet">]</span></a></sup> résume les sentiments des protagonistes : <span class="citation">« Une fois l'équivalence de la récursivité générale et de la λ-définissabilité établie, Church, Kleene et moi nous attendions à ce que Gödel nous rejoigne pour supporter la thèse de Church. Gödel avait cependant encore des réserves et ce n'est qu'au moins deux ou trois ans plus tard, après les travaux de Turing, que Gödel devint finalement un adepte (comme le devint aussi Turing). »</span> </p><p>Turing écrit<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite_crochet">[</span>λdef 2<span class="cite_crochet">]</span></a></sup> en <a href="/wiki/1937" title="1937">1937</a> : <span class="citation">« L'identification des fonctions « effectivement calculables » avec les fonctions calculables [c-à-d. définies par une machine de Turing] est peut-être plus convaincante que l'identification avec les fonctions λ-définissables ou récursives générales. Pour ceux qui adoptent ce point de vue, la démonstration formelle de l'équivalence fournit une justification du calcul de Church et permet de remplacer les 'machines' qui engendrent des fonctions calculables par les λ-définitions qui sont plus commodes. »</span> </p><p>Les historiens ont tendance à oublier les travaux de <a href="/wiki/Emil_Post" title="Emil Post">Post</a>, à la même époque, qui publia une première <i>thèse sur la calculabilité</i> en 1920, qu'il prolongea en 1936<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite_crochet">[</span>11<span class="cite_crochet">]</span></a></sup><sup class="reference cite_virgule">,</sup><sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite_crochet">[</span>12<span class="cite_crochet">]</span></a></sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Des_fonctions_et_nombres_non_calculables">Des fonctions et nombres non calculables</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=5" title="Modifier la section : Des fonctions et nombres non calculables" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=5" title="Modifier le code source de la section : Des fonctions et nombres non calculables"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>On peut définir très formellement des fonctions (par exemple sur les entiers naturels) qui ne sont pas calculables. Elles prennent en général des valeurs tellement grandes que l'on ne peut pas les calculer et par conséquent on ne peut même pas « exprimer » les valeurs qu'elles prennent, car c'est leur définition qui le dit. La plus connue est celle dite du <a href="/wiki/Castor_affair%C3%A9" title="Castor affairé">castor affairé</a>. Pour simplifier, il s'agit de la taille du plus grand travail que peut faire une machine de Turing quand on lui donne une ressource limitée par <i>n</i>. Comme sa définition est obtenue comme une limite de ce que pourraient faire les machines de Turing, le nombre qu'elle produit ne peut pas être calculé, ni même sa valeur exacte exprimée, tout au plus les chercheurs arrivent-ils à donner des nombres qui lui sont inférieurs pour les plus petites valeurs de <i>n</i> (2, 3, 4, 5, péniblement 6). </p><p>Le nombre <a href="/wiki/Om%C3%A9ga_de_Chaitin" title="Oméga de Chaitin">Oméga de Chaitin</a> est un <a href="/wiki/Nombre_r%C3%A9el" title="Nombre réel">nombre réel</a> parfaitement défini qui n'est pas calculable, précisément parce que sa construction dépend des réponses au <a href="/wiki/Probl%C3%A8me_de_l%27arr%C3%AAt" title="Problème de l'arrêt">problème semi-décidable de l'arrêt des machines de Turing</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Autres_modèles_de_calcul"><span id="Autres_mod.C3.A8les_de_calcul"></span>Autres modèles de calcul</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=6" title="Modifier la section : Autres 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%A8se_de_Church&action=edit&section=6" title="Modifier le code source de la section : Autres modèles de calcul"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>On ne connaît pas de modèle de calcul plus puissant que les machines de Turing, c'est-à-dire qui serait en mesure de calculer des fonctions non-calculables par une machine de Turing. La thèse de Church physique pourrait être remise en cause par l'<a href="/wiki/Hypercalcul" title="Hypercalcul">hypercalcul</a>, mais les processus physiques utilisés par l'hypercalcul sont extrêmement spéculatifs et probablement à jamais impossibles à mettre en œuvre en pratique. </p><p>Inversement, il existe des modèles de calcul plus faibles que les machines de Turing. Par exemple la définition des <a href="/wiki/Fonction_r%C3%A9cursive_primitive" title="Fonction récursive primitive">fonctions récursives primitives</a> propose implicitement un modèle de calcul : essentiellement celui des définitions par récurrence sur un paramètre. Or la <a href="/wiki/Fonction_d%27Ackermann" title="Fonction d'Ackermann">fonction d'Ackermann</a> est calculable, mais n'est pas récursive primitive. </p><p>Plus généralement, un <a href="/wiki/Syst%C3%A8me_formel" title="Système formel">système formel</a> (comme un <a href="/wiki/Langage_de_programmation" title="Langage de programmation">langage de programmation</a>) qui ne permet de définir que des <i>fonctions totales</i> (comme Gallina le langage de <a href="/wiki/Coq_(logiciel)" title="Coq (logiciel)">Coq</a> ou <a href="/w/index.php?title=Agda_(programming_language)&action=edit&redlink=1" class="new" title="Agda (programming language) (page inexistante)">Agda</a> <a href="https://en.wikipedia.org/wiki/Agda_(programming_language)" class="extiw" title="en:Agda (programming language)"><span class="indicateur-langue" title="Article en anglais : « Agda (programming language) »">(en)</span></a>), c'est-à-dire que le calcul de ces fonctions s'arrête quelle que soit l'entrée, ne peut pas être candidat à la thèse de Church, autrement dit, il n'est pas <a href="/wiki/Turing-complet" title="Turing-complet">Turing-complet</a>. La fonction d'évaluation des fonctions définies dans un système formel ne peut être définie dans ce même système formel. Par exemple, le système du <a href="/wiki/Calcul_des_constructions" title="Calcul des constructions">calcul des constructions</a>, bien qu'extrêmement riche et général (on peut pratiquement y formaliser toutes les mathématiques) ne peut pas être candidat à la thèse de Church, car il ne définit que des fonctions normalisantes, c'est-à-dire des fonctions dont le calcul s'arrête pour toute entrée<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite_crochet">[</span>13<span class="cite_crochet">]</span></a></sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Thèse_de_Church_et_calcul_quantique"><span id="Th.C3.A8se_de_Church_et_calcul_quantique"></span>Thèse de Church et <a href="/wiki/Calcul_quantique" class="mw-redirect" title="Calcul quantique">calcul quantique</a></h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=7" title="Modifier la section : Thèse de Church et calcul quantique" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=7" title="Modifier le code source de la section : Thèse de Church et calcul quantique"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Les différents modèles de calcul purement mathématiques élaborés pour modéliser la calculabilité ne prennent pas en compte de processus physiques. Comme l'ont montré <a href="/wiki/Robin_Gandy" title="Robin Gandy">Robin Gandy</a><sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite_crochet">[</span>14<span class="cite_crochet">]</span></a></sup> , <a href="/w/index.php?title=Nachum_Dershowitz&action=edit&redlink=1" class="new" title="Nachum Dershowitz (page inexistante)">Nachum Dershowitz</a> <a href="https://en.wikipedia.org/wiki/Nachum_Dershowitz" class="extiw" title="en:Nachum Dershowitz"><span class="indicateur-langue" title="Article en anglais : « Nachum Dershowitz »">(en)</span></a> et <a href="/w/index.php?title=Yuri_Gurevich&action=edit&redlink=1" class="new" title="Yuri Gurevich (page inexistante)">Yuri Gurevich</a> <a href="https://en.wikipedia.org/wiki/Yuri_Gurevich" class="extiw" title="en:Yuri Gurevich"><span class="indicateur-langue" title="Article en anglais : « Yuri Gurevich »">(en)</span></a><sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite_crochet">[</span>15<span class="cite_crochet">]</span></a></sup> les considérations physiques ne sont pas négligeables. Or, d'après le <a href="/wiki/Principe_de_Church-Turing-Deutsch" title="Principe de Church-Turing-Deutsch">Principe de Church-Turing-Deutsch</a>, tout processus physique fini peut être simulé par un mécanisme physique fini. C'est donc pour cela que l'informatique s'inspire de la <a href="/wiki/Physique_classique" title="Physique classique">physique classique</a>, et utilise des bits et non des qbits (le modèle quantique "rompt le charme de la thèse de Church-Turing étendue"<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite_crochet">[</span>16<span class="cite_crochet">]</span></a></sup>). </p><p>En 1982, le physicien <a href="/wiki/Richard_Feynman" title="Richard Feynman">Richard Feynman</a> s'est posé la question de savoir si les modèles de calcul pouvaient calculer l'évolution de processus quantiques. Il est parvenu à démontrer que cela était possible, mais de manière inefficace, inapplicable en pratique. Or, la nature est visiblement capable de « calculer » cette évolution de manière efficace. La question se pose donc inévitablement de savoir si les processus quantiques sont en relation avec une autre forme de calculabilité et s'ils remettent en cause la forme physique de la thèse de Church. </p><p>Pour explorer cette question, il est nécessaire d'élaborer un modèle de calcul prenant en compte les particularités de la <a href="/wiki/M%C3%A9canique_quantique" title="Mécanique quantique">mécanique quantique</a>, et capable de calculer les processus quantiques efficacement. Muni de ce modèle mathématique, on peut alors étudier ses relations avec les modèles classiques de calcul, sur le plan de la calculabilité (ce que les modèles sont capables de calculer ou non), l'universalité (si une machine peut simuler toutes les autres efficacement), et 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)">complexité</a> (dans quels ordres de temps et de mémoire les problèmes peuvent-ils être calculés). </p><p>Les premières tentatives de créer des modèles de calcul quantiques ont eu lieu au début des années 1980 par <a href="/w/index.php?title=Paul_Benioff&action=edit&redlink=1" class="new" title="Paul Benioff (page inexistante)">Paul Benioff</a><sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite_crochet">[</span>17<span class="cite_crochet">]</span></a></sup>. C'était un modèle de machine de Turing <i>réversible</i>, prenant en compte une des particularités majeures de la mécanique quantique : l'<a href="/wiki/Unitarit%C3%A9" title="Unitarité">unitarité</a> qui implique que les calculs quantiques doivent être réversibles (contrairement aux calculs classiques). C'est-à-dire que, connaissant un résultat et la série d'opérations y ayant mené, un calcul quantique peut toujours être déroulé en arrière jusqu'à retrouver les données initiales<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite_crochet">[</span>18<span class="cite_crochet">]</span></a></sup>. Mais il manquait encore des ingrédients pour aboutir à un véritable modèle de calcul quantique : même si les calculs utilisaient la <a href="/wiki/Superposition_quantique" class="mw-redirect" title="Superposition quantique">superposition quantique</a>, les états des bits à chaque étape de calcul étaient dans un état classique « 0 » ou bien « 1 ». </p><p>En 1985, <a href="/wiki/David_Deutsch" title="David Deutsch">David Deutsch</a> propose un véritable modèle de calcul quantique<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite_crochet">[</span>19<span class="cite_crochet">]</span></a></sup>, reconnu comme étant le premier véritable modèle de <a href="/w/index.php?title=Machine_de_Turing_quantique&action=edit&redlink=1" class="new" title="Machine de Turing quantique (page inexistante)">machine de Turing quantique</a><sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite_crochet">[</span>20<span class="cite_crochet">]</span></a></sup>. Dans cet article, Deutsch remarque que les calculateurs quantiques sont capables de produire un résultat que les machines de Turing classiques ne peuvent produire : générer un <a href="/wiki/Suite_al%C3%A9atoire" title="Suite aléatoire">nombre purement aléatoire</a>. Mais cela ne remet pas en cause la thèse de Church, car la génération d'un nombre aléatoire ne fait pas partie de ce qui est considéré comme un « calcul ». </p><p>Ce modèle de calcul a permis d'établir que les machines de Turing quantiques ne permettent pas de résoudre davantage de problèmes que les machines de Turing classiques. Elles sont même, d'un certain point de vue, moins complètes que les machines de Turing classiques car, si on désire utiliser le parallélisme quantique pour calculer plus rapidement certaines propriétés conjointes entre <i>m</i> valeurs binaires, alors il a été démontré en 1991 par <a href="/wiki/Richard_Jozsa" title="Richard Jozsa">Richard Jozsa</a><sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite_crochet">[</span>21<span class="cite_crochet">]</span></a></sup> que seules <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 2^{2^{m}}-2^{m+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> </mrow> </msup> <mo>−</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{2^{m}}-2^{m+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bd8483c5363ab7b5b6d4d87cb3238a318345fa22" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle 2^{2^{m}}-2^{m+1}}"></span> propriétés parmi les <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 2^{2^{m}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{2^{m}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f19c0381836632650b41f63528daceb55825f690" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.552ex; height:2.676ex;" alt="{\displaystyle 2^{2^{m}}}"></span> propriétés conjointes possibles étaient calculables de cette manière, alors qu'elles le sont toutes avec une machine de Turing classique<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite_crochet">[</span>22<span class="cite_crochet">]</span></a></sup>. </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%A8se_de_Church&veaction=edit&section=8" 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%A8se_de_Church&action=edit&section=8" 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="mw-heading mw-heading3"><h3 id="Notes">Notes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=9" title="Modifier la section : Notes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=9" title="Modifier le code source de la section : Notes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style="column-width:36em; column-count:2;"><ol class="references"> <li id="cite_note-11"><span class="mw-cite-backlink noprint"><a href="#cite_ref-11">↑</a> </span><span class="reference-text"><abbr class="abbr" title="pages">pp.</abbr>  153-163. ; voir aussi <i>Collected Works of A.M. Turing</i>, tome <i>Mathematical Logic</i>.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink noprint"><a href="#cite_ref-14">↑</a> </span><span class="reference-text">dans cet article</span> </li> </ol> </div> <div class="mw-heading mw-heading3"><h3 id="Références"><span id="R.C3.A9f.C3.A9rences"></span>Références</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=10" title="Modifier la section : Références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=10" title="Modifier le code source de la section : Références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="references-small decimal" style="column-width:36em; column-count:2;"><ol class="references"> <li id="cite_note-Dowek-1"><span class="mw-cite-backlink noprint">↑ <sup><a href="#cite_ref-Dowek_1-0">a</a> et <a href="#cite_ref-Dowek_1-1">b</a></sup> </span><span class="reference-text"><span class="ouvrage" id="Dowek2007"><span class="ouvrage" id="Gilles_Dowek2007"><a href="/wiki/Gilles_Dowek" title="Gilles Dowek">Gilles <span class="nom_auteur">Dowek</span></a>, <cite class="italique">Les Métamorphoses du calcul : Une étonnante histoire des mathématiques</cite>, Le Pommier, <time>2007</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/978-2746503243" title="Spécial:Ouvrages de référence/978-2746503243"><span class="nowrap">978-2746503243</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=Les+M%C3%A9tamorphoses+du+calcul&rft.pub=Le+Pommier&rft.stitle=Une+%C3%A9tonnante+histoire+des+math%C3%A9matiques&rft.aulast=Dowek&rft.aufirst=Gilles&rft.date=2007&rft.isbn=978-2746503243&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink noprint"><a href="#cite_ref-2">↑</a> </span><span class="reference-text">voir Robert I. Soare, article cité.</span> </li> <li id="cite_note-3"><span class="mw-cite-backlink noprint"><a href="#cite_ref-3">↑</a> </span><span class="reference-text">Attesté pas une lettre de Church à Gödel de 1934, voir Soare, article cité.</span> </li> <li id="cite_note-Vollat-4"><span class="mw-cite-backlink noprint"><a href="#cite_ref-Vollat_4-0">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Vollat1989"><span class="ouvrage" id="P._Vollat1989">P. Vollat, <cite class="italique">Calculabilité effective et algorithmique théorique Broché</cite>, Eyrolles, <time>1989</time>, 186 <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/2212081685" title="Spécial:Ouvrages de référence/2212081685"><span class="nowrap">2212081685</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+effective+et+algorithmique+th%C3%A9orique+Broch%C3%A9&rft.pub=Eyrolles&rft.aulast=Vollat&rft.aufirst=P.&rft.date=1989&rft.tpages=186&rft.isbn=2212081685&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></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="Pégny2012"><span class="ouvrage" id="Maël_Pégny2012">Maël <span class="nom_auteur">Pégny</span>, « <cite style="font-style:normal">Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul</cite> », <i>Philosophia Scientiæ. Travaux d'histoire et de philosophie des sciences</i>, <abbr class="abbr" title="numéros">n<sup>os</sup></abbr> 16-3,‎ <time class="nowrap" datetime="2012-11-01" data-sort-value="2012-11-01"><abbr class="abbr" title="premier">1<sup>er</sup></abbr> novembre 2012</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">39–67</span> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Serial_Number" title="International Standard Serial Number">ISSN</a> <span class="plainlinks noarchive"><a rel="nofollow" class="external text" href="https://portal.issn.org/resource/issn/1281-2463">1281-2463</a></span>, <a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.4000/philosophiascientiae.769">10.4000/philosophiascientiae.769</a></span>, <a rel="nofollow" class="external text" href="http://journals.openedition.org/philosophiascientiae/769">lire en ligne</a>, consulté le <time class="nowrap" datetime="2020-01-07" data-sort-value="2020-01-07">7 janvier 2020</time>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Les+deux+formes+de+la+th%C3%A8se+de+Church-Turing+et+l%E2%80%99%C3%A9pist%C3%A9mologie+du+calcul&rft.jtitle=Philosophia+Scienti%C3%A6.+Travaux+d%27histoire+et+de+philosophie+des+sciences&rft.issue=16-3&rft.aulast=P%C3%A9gny&rft.aufirst=Ma%C3%ABl&rft.date=2012-11-01&rft.pages=39%E2%80%9367&rft.issn=1281-2463&rft_id=info%3Adoi%2F10.4000%2Fphilosophiascientiae.769&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink noprint"><a href="#cite_ref-8">↑</a> </span><span class="reference-text">cité dans <a rel="nofollow" class="external text" href="https://www.cmu.edu/dietrich/philosophy/docs/tech-reports/175_Sieg.pdf">Wilfried Sieg, 2005, <i>Church without dogma: axioms for computability,</i> Carnegie Mellon University</a> p. 4</span> </li> <li id="cite_note-Church36-9"><span class="mw-cite-backlink noprint">↑ <sup><a href="#cite_ref-Church36_9-0">a</a> et <a href="#cite_ref-Church36_9-1">b</a></sup> </span><span class="reference-text">Alonzo Church: A Note on the Entscheidungsproblem. J. Symb. Log. 1(1): 40-41 (1936)</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink noprint"><a href="#cite_ref-10">↑</a> </span><span class="reference-text"><a rel="nofollow" class="external text" href="https://books.google.fr/books?id=iivdLjhYImAC&pg=PA709&lpg=PA709&dq=1935+conference+church+american+mathematical+soci%C3%A9ty&source=bl&ots=DvMysEwrPq&sig=WfA6KB2b5yp1v6bhqDrnJoo2VUw&hl=fr&sa=X&ved=0ahUKEwiEtLqotebXAhVJLcAKHbgpAeIQ6AEIKzAA#v=onepage&q=1935%20conference%20church%20american%20mathematical%20soci%C3%A9ty&f=false">Robert I. Soare: Computability and Incomputability. CiE 2007: 705-715.</a></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink noprint"><a href="#cite_ref-12">↑</a> </span><span class="reference-text">La terminologie est due à Church.</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink noprint"><a href="#cite_ref-13">↑</a> </span><span class="reference-text">In <i>Highlights of the History of the Lambda-Calculus</i>, <i>Annals of the History of Computing</i> vol. 6, n°4, oct 1984.</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink noprint"><a href="#cite_ref-15">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Post1936"><span class="ouvrage" id="Emil_Post1936"><a href="/wiki/Emil_Post" title="Emil Post">Emil Post</a>, « <cite style="font-style:normal">Finite combinatory processes - Formulation 1</cite> », <i>The Journal of Symbolic Logic 1</i>, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 3,‎ <time>1936</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">103–105</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Finite+combinatory+processes+-+Formulation+1&rft.jtitle=The+Journal+of+Symbolic+Logic+1&rft.issue=3&rft.aulast=Post&rft.aufirst=Emil&rft.date=1936&rft.pages=103%E2%80%93105&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span>.</span> </li> <li id="cite_note-16"><span class="mw-cite-backlink noprint"><a href="#cite_ref-16">↑</a> </span><span class="reference-text">Pour une discussion de la contribution d'<a href="/wiki/Emil_Post" title="Emil Post">Emil Post</a>, on lira <span class="ouvrage" id="de_Mol2013"><span class="ouvrage" id="Liesbeth_de_Mol2013">Liesbeth de Mol, <cite style="font-style:normal">« Generating, solving and the mathematics of Homo Sapiens. Emil Post’s views on computation »</cite>, dans Hector Zenil, <cite class="italique">A computable universe. Understanding Computation and Exploring Nature As Computation,</cite>, World Scientific, <time>2013</time>, 978-981-4374-29-3 <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://hal.univ-lille.fr/hal-01396500v1">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=bookitem&rft.btitle=A+computable+universe.+Understanding+Computation+and+Exploring+Nature+As+Computation%2C&rft.atitle=Generating%2C+solving+and+the+mathematics+of+Homo+Sapiens.+Emil+Post%E2%80%99s+views%0Aon+computation&rft.pub=World+Scientific&rft.au=Liesbeth+de+Mol&rft.date=2013&rft.tpages=978-981-4374-29-3&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span>.</span> </li> <li id="cite_note-17"><span class="mw-cite-backlink noprint"><a href="#cite_ref-17">↑</a> </span><span class="reference-text"> <span class="ouvrage" id="BertodCasteran"><span class="ouvrage" id="Yves_BertodPierre_Casteran">Yves <span class="nom_auteur">Bertod</span> et Pierre <span class="nom_auteur">Casteran</span>, <cite class="italique">Interactive Theorem Proving and Program development</cite> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.labri.fr/perso/casteran/CoqArt/coqartF.pdf">lire en ligne</a>)</small>, « 2.1 »<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Interactive+Theorem+Proving+and+Program+development&rft.aulast=Bertod&rft.aufirst=Yves&rft.au=Casteran%2C+Pierre&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink noprint"><a href="#cite_ref-18">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Gandy1980"><span class="ouvrage" id="Robin_Gandy1980">Robin Gandy, « <cite style="font-style:normal">Church's Thesis and Principles for Mechanisms</cite> », <i>Studies in Logic and the Foundations of Mathematics</i>,‎ <time>1980</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">123-148</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0049237X08712576">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=Church%27s+Thesis+and+Principles+for+Mechanisms&rft.jtitle=Studies+in+Logic+and+the+Foundations+of+Mathematics&rft.aulast=Gandy&rft.aufirst=Robin&rft.date=1980&rft.pages=123-148&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink noprint"><a href="#cite_ref-19">↑</a> </span><span class="reference-text"> <span class="ouvrage" id="DershowitzGurevich2008"><span class="ouvrage" id="Nachum_DershowitzYuri_Gurevich2008">Nachum Dershowitz et Yuri Gurevich, « <cite style="font-style:normal">A natural axiomatization of computability and proof of Church's Thesis</cite> », <i>Bull. Symbolic Logic</i>, <abbr class="abbr" title="volume">vol.</abbr> 14, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 3,‎ <time>2008</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">299 - 350</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://projecteuclid.org/euclid.bsl/1231081370">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=A+natural+axiomatization+of+computability+and+proof+of+Church%27s+Thesis&rft.jtitle=Bull.+Symbolic+Logic&rft.issue=3&rft.aulast=Dershowitz&rft.aufirst=Nachum&rft.au=Yuri+Gurevich&rft.date=2008&rft.volume=14&rft.pages=299+-+350&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink noprint"><a href="#cite_ref-20">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Pégny2013"><span class="ouvrage" id="Maël_Pégny2013">Maël <span class="nom_auteur">Pégny</span>, <cite class="italique">Sur les limites empiriques du calcul : calculabilité, complexité et physique</cite>, Paris 1, <time class="nowrap" datetime="2013-12-05" data-sort-value="2013-12-05">5 décembre 2013</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.theses.fr/2013PA010673">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=Sur+les+limites+empiriques+du+calcul+%3A+calculabilit%C3%A9%2C+complexit%C3%A9+et+physique&rft.pub=Paris+1&rft.aulast=P%C3%A9gny&rft.aufirst=Ma%C3%ABl&rft.date=2013-12-05&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span><sup class="need_ref_tag" style="padding-left:2px;"><a href="/wiki/Aide:R%C3%A9f%C3%A9rence_incompl%C3%A8te" title="Aide:Référence incomplète">[réf. incomplète]</a></sup></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink noprint"><a href="#cite_ref-21">↑</a> </span><span class="reference-text">P. Bénioff, « <i><span class="lang-en" lang="en">The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines</span></i> », <i><span class="lang-en" lang="en">Journal of Statistical Physics</span></i>, Volume 22 (1980), pp. 563-591.</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink noprint"><a href="#cite_ref-22">↑</a> </span><span class="reference-text">Ce qui est impossible avec un calcul classique : connaissant un résultat « 10 » par exemple, et l'opération y ayant mené, l'addition, on est incapable de savoir si les données initiales étaient « 5 » et « 5 » ou « 9 » et « 1 » par exemple.</span> </li> <li id="cite_note-23"><span class="mw-cite-backlink noprint"><a href="#cite_ref-23">↑</a> </span><span class="reference-text">D. Deutsch <i>Quantum Therory, the Church-Turing Principle, and the Universal Quantum Computer</i> Proc. R. Soc. Lond. A, Volume 400 (1985) pp. 97-117</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink noprint"><a href="#cite_ref-24">↑</a> </span><span class="reference-text">Colin. P. Williams <i>Explorations in Quantum Computing</i> Springer. 2d édition 2011</span> </li> <li id="cite_note-25"><span class="mw-cite-backlink noprint"><a href="#cite_ref-25">↑</a> </span><span class="reference-text">R. Jozsa, « <i><span class="lang-en" lang="en">Characterizing Classes of Functions Computable by Quantum Parallelism</span></i> », <i><span class="lang-en" lang="en">Proc. R. Soc. Lond. A</span></i>, Volume 435 (1991) pp. 563-574.</span> </li> <li id="cite_note-26"><span class="mw-cite-backlink noprint"><a href="#cite_ref-26">↑</a> </span><span class="reference-text">Mais, évidemment, une machine de Turing quantique pouvant simuler une machine de Turing classique, une machine de Turing quantique est capable de calculer toutes les propriétés conjointes, mais sans utiliser ses propriétés propres.</span> </li> </ol> </div> <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%A8se_de_Church&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%A8se_de_Church&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> <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%A8se_de_Church&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%A8se_de_Church&action=edit&section=12" title="Modifier le code source de la section : Articles connexes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Calculabilit%C3%A9" class="mw-redirect" title="Calculabilité">Calculabilité</a></li> <li><a href="/wiki/Computationnalisme" title="Computationnalisme">Computationnalisme</a></li> <li><a href="/wiki/R%C3%A9sultats_effectifs_en_th%C3%A9orie_des_nombres" title="Résultats effectifs en théorie des nombres">Résultats effectifs en théorie des nombres</a></li> <li><a href="/wiki/Algorithme_probabiliste" title="Algorithme probabiliste">Algorithme probabiliste</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Sources">Sources</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=13" title="Modifier la section : Sources" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=13" title="Modifier le code source de la section : Sources"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="ouvrage" id="Delahaye1991"><span class="ouvrage" id="Jean-Paul_Delahaye1991"><a href="/wiki/Jean-Paul_Delahaye" title="Jean-Paul Delahaye">Jean-Paul <span class="nom_auteur">Delahaye</span></a>, « <cite style="font-style:normal">Le concept de suite aléatoire et la thèse de Church</cite> », <i>Séminaire de philosophie et de mathématiques</i>,‎ <time>1991</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.numdam.org/article/SPHM_1991___3_A1_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=Le+concept+de+suite+al%C3%A9atoire+et+la+th%C3%A8se+de+Church&rft.jtitle=S%C3%A9minaire+de+philosophie+et+de+math%C3%A9matiques&rft.aulast=Delahaye&rft.aufirst=Jean-Paul&rft.date=1991&rft_id=http%3A%2F%2Fwww.numdam.org%2Farticle%2FSPHM_1991___3_A1_0.pdf&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span>:</li></ul> <div class="references-small decimal" style="column-width:24em; column-count:3;"><ol class="references"> <li id="cite_note-6"><span class="mw-cite-backlink noprint"><a href="#cite_ref-6">↑</a> </span><span class="reference-text">p. 22</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink noprint"><a href="#cite_ref-7">↑</a> </span><span class="reference-text">p. 3</span> </li> </ol> </div> <div class="mw-heading mw-heading4"><h4 id="Articles_originaux">Articles originaux</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=14" title="Modifier la section : Articles originaux" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=14" title="Modifier le code source de la section : Articles originaux"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><i><span class="ouvrage" id="Church1935"><span class="ouvrage" id="Alonzo_Church1935"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo <span class="nom_auteur">Church</span></a>, « <cite style="font-style:normal" lang="en">An Unsolvable Problem of Elementary Number Theory (abstract)</cite> », <i><span class="lang-en" lang="en">Bull. Amer. Math. Soc.</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 41,‎ <time>1935</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">332-333</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=An+Unsolvable+Problem+of+Elementary+Number+Theory+%28abstract%29&rft.jtitle=Bull.+Amer.+Math.+Soc.&rft.aulast=Church&rft.aufirst=Alonzo&rft.date=1935&rft.volume=41&rft.pages=332-333&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></i> (abstract), Bull. Amer. Math. Soc. 41 (1935), <abbr class="abbr" title="page(s)">p.</abbr> 332-333.</li> <li><span class="ouvrage" id="Church1936"><span class="ouvrage" id="Alonzo_Church1936"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo <span class="nom_auteur">Church</span></a>, « <cite style="font-style:normal" lang="en">An Unsolvable Problem of Elementary Number Theory</cite> », <i><span class="lang-en" lang="en">American Journal of Mathematics</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 58,‎ <time>1936</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">245–63</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=An+Unsolvable+Problem+of+Elementary+Number+Theory&rft.jtitle=American+Journal+of+Mathematics&rft.aulast=Church&rft.aufirst=Alonzo&rft.date=1936&rft.volume=58&rft.pages=245%E2%80%9363&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li><span class="ouvrage" id="Church1936"><span class="ouvrage" id="Alonzo_Church1936"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo <span class="nom_auteur">Church</span></a>, « <cite style="font-style:normal" lang="en">A Note on the Entscheidungsproblem</cite> », <i><span class="lang-en" lang="en">Journal of Symbolic Logic</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 1,‎ <time>1936</time>, <abbr class="abbr" title="page(s)">p.</abbr> 40-41, correction <abbr class="abbr" title="page(s)">p.</abbr> 101-102.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=A+Note+on+the+Entscheidungsproblem&rft.jtitle=Journal+of+Symbolic+Logic&rft.aulast=Church&rft.aufirst=Alonzo&rft.date=1936&rft.volume=1&rft.pages=40-41%2C+correction+%3Cabbr+class%3D%22abbr%22+title%3D%22page%28s%29%22%3Ep.%3C%2Fabbr%3E%26nbsp%3B101-102.&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li>Notes de cours de <a href="/wiki/Stephen_Kleene" class="mw-redirect" title="Stephen Kleene">Kleene</a> et Rosser. Rééditée dans <span class="ouvrage" id="Gödel1934"><span class="ouvrage" id="Kurt_Gödel1934"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> [[<a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a>|Kurt <span class="nom_auteur">Gödel</span>]], « <cite style="font-style:normal" lang="en">On Undecidable Propositions of Formal Mathematical Systems</cite> », <i><span class="lang-en" lang="en"><i>The Undecidable</i></span></i>, Davis, M. (New York: Raven Press),‎ 1934, rééditées en 1965<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=On+Undecidable+Propositions+of+Formal+Mathematical+Systems&rft.jtitle=%27%27The+Undecidable%27%27&rft.aulast=G%C3%B6del&rft.aufirst=Kurt&rft.date=1965&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li><span class="ouvrage" id="Herbrand1931"><span class="ouvrage" id="Jacques_Herbrand1931"><a href="/wiki/Jacques_Herbrand" title="Jacques Herbrand">Jacques <span class="nom_auteur">Herbrand</span></a>, « <cite style="font-style:normal">Sur la non-contradiction de l'arithmétique</cite> », <i><span class="lang-de" lang="de"><a href="/wiki/Journal_fur_die_reine_und_angewandte_Mathematik" class="mw-redirect" title="Journal fur die reine und angewandte Mathematik">Journal fur die reine und angewandte Mathematik</a></span></i>, <abbr class="abbr" title="volume">vol.</abbr> 166,‎ <time>1931</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">1-8</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.digizeitschriften.de/dms/toc/?PPN=PPN243919689_0166#">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=Sur+la+non-contradiction+de+l%27arithm%C3%A9tique&rft.jtitle=Journal+fur+die+reine+und+angewandte+Mathematik&rft.aulast=Herbrand&rft.aufirst=Jacques&rft.date=1931&rft.volume=166&rft.pages=1-8&rft_id=http%3A%2F%2Fwww.digizeitschriften.de%2Fdms%2Ftoc%2F%3FPPN%3DPPN243919689_0166%23&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li><span class="ouvrage" id="Kleene1936"><span class="ouvrage" id="Stephen_Cole_Kleene1936"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Stephen_Kleene" class="mw-redirect" title="Stephen Kleene">Stephen Cole <span class="nom_auteur">Kleene</span></a>, « <cite style="font-style:normal" lang="en">Lambda-Definability and Recursiveness</cite> », <i><span class="lang-en" lang="en"><a href="/wiki/Duke_Mathematical_Journal" title="Duke Mathematical Journal">Duke Mathematical Journal</a></span></i>, <abbr class="abbr" title="volume">vol.</abbr> 2,‎ <time>1936</time>, <abbr class="abbr" title="page(s)">p.</abbr> 340-353.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Lambda-Definability+and+Recursiveness&rft.jtitle=Duke+Mathematical+Journal&rft.aulast=Kleene&rft.aufirst=Stephen+Cole&rft.date=1936&rft.volume=2&rft.pages=340-353.&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li><span class="ouvrage" id="Kleene1943"><span class="ouvrage" id="Stephen_Cole_Kleene1943"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Stephen_Kleene" class="mw-redirect" title="Stephen Kleene">Stephen Cole <span class="nom_auteur">Kleene</span></a>, « <cite style="font-style:normal" lang="en">Recursive predicates and quantifiers</cite> », <i><span class="lang-en" lang="en">Trans. A.M.S.</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 53,‎ <time>1943</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">41-73</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Recursive+predicates+and+quantifiers&rft.jtitle=Trans.+A.M.S.&rft.aulast=Kleene&rft.aufirst=Stephen+Cole&rft.date=1943&rft.volume=53&rft.pages=41-73&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li> <li><span class="ouvrage" id="Turing1937"><span class="ouvrage" id="Alan_Turing1937"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alan_Turing" title="Alan Turing">Alan <span class="nom_auteur">Turing</span></a>, « <cite style="font-style:normal" lang="en">On Computable Numbers, with an Application to the Entscheidungsproblem</cite> », <i><a href="/wiki/London_Mathematical_Society#Publications" title="London Mathematical Society"><span class="lang-en" lang="en">Proc. London Math. Soc.</span></a></i>, <abbr class="abbr" title="deuxième">2<sup>e</sup></abbr> série, <abbr class="abbr" title="volume">vol.</abbr> 42,‎ <time>1937</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">230-265</span> <small style="line-height:1em;">(<a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1112/plms/s2-42.1.230">10.1112/plms/s2-42.1.230</a></span>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=On+Computable+Numbers%2C+with+an+Application+to+the+Entscheidungsproblem&rft.jtitle=Proc.+London+Math.+Soc.&rft.aulast=Turing&rft.aufirst=Alan&rft.date=1937&rft.volume=42&rft.pages=230-265&rft_id=info%3Adoi%2F10.1112%2Fplms%2Fs2-42.1.230&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span> et <span class="ouvrage" id="1938">« <cite style="font-style:normal">[<i>idem</i>] : A Correction</cite> », <i>Proc. London Math. Soc.</i>, <abbr class="abbr" title="deuxième">2<sup>e</sup></abbr> série, <abbr class="abbr" title="volume">vol.</abbr> 43,‎ <time>1938</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">544-546</span> <small style="line-height:1em;">(<a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1112/plms/s2-43.6.544">10.1112/plms/s2-43.6.544</a></span>, <a rel="nofollow" class="external text" href="http://www.thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=%5B%27%27idem%27%27%5D&rft.jtitle=Proc.+London+Math.+Soc.&rft.stitle=A+Correction&rft.date=1938&rft.volume=43&rft.pages=544-546&rft_id=info%3Adoi%2F10.1112%2Fplms%2Fs2-43.6.544&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></li> <li><span class="ouvrage" id="Turing1937"><span class="ouvrage" id="Alan_Turing1937"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="/wiki/Alan_Turing" title="Alan Turing">Alan <span class="nom_auteur">Turing</span></a>, « <cite style="font-style:normal" lang="en">Computability and λ-definability</cite> », <i><span class="lang-en" lang="en">J. Symbolic Logic</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 2,‎ <time>1937</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">153-163</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Computability+and+%CE%BB-definability&rft.jtitle=J.+Symbolic+Logic&rft.aulast=Turing&rft.aufirst=Alan&rft.date=1937&rft.volume=2&rft.pages=153-163&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATh%C3%A8se+de+Church"></span></span></span></li></ul> <div class="mw-heading mw-heading4"><h4 id="Autres_(en_anglais)"><span id="Autres_.28en_anglais.29"></span>Autres (en anglais)</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=15" title="Modifier la section : Autres (en anglais)" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=15" title="Modifier le code source de la section : Autres (en anglais)"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Martin_Davis" title="Martin Davis">Martin Davis</a> editor, <i>The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions</i>, Raven Press, New York, 1965. Les articles originaux dont ceux de Gödel, Church, Turing, Rosser, Kleene, and Post. Préfaces de Davis.</li> <li><a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Cole Kleene</a>, 1952, <i>Introduction to Metamathematics</i>, Van Nostrand, New York.</li> <li><a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Cole Kleene</a>, <i>Origins of Recursive Function Theory</i> in <i>Annals of the History of Computing</i>, Vol. 3 No. 1, <time class="nowrap" datetime="1981-01" data-sort-value="1981-01">janvier 1981</time>.</li> <li><a href="/wiki/Barkley_Rosser" class="mw-redirect" title="Barkley Rosser">Barkley Rosser</a> <i>Highlights of the History of the Lambda-Calculus</i>, Annals of the History of Computing 6,4 [1984], 337-349</li> <li>Robert Soare, (1995-6), <i>Computability and Recursion</i>, Bulletin of Symbolic Logic 2 (1996), 284--321, <a rel="nofollow" class="external text" href="http://www.people.cs.uchicago.edu/~soare/History/compute.pdf">version en ligne</a>, article sur l'historique de la calculabilité, qui milite pour un certain nombre de changements terminologiques, écrit par un spécialiste du domaine.</li> <li>Wilfried Sieg <i>Step by recursive step: Church's analysis of effective calculability</i>. Bulletin of Symbolic Logic 3(2): 154-180 (1997).</li> <li><i>Collected Works of A. M. Turing</i> vol. <i>Mathematical Logic</i>, eds. R. O. Gandy and C. E. M. Yates, <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/0-444-50423-0" title="Spécial:Ouvrages de référence/0-444-50423-0"><span class="nowrap">0-444-50423-0</span></a>)</small>.</li></ul> <div class="mw-heading mw-heading4"><h4 id="Autres_(en_français)"><span id="Autres_.28en_fran.C3.A7ais.29"></span>Autres (en français)</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Th%C3%A8se_de_Church&veaction=edit&section=16" title="Modifier la section : Autres (en français)" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Th%C3%A8se_de_Church&action=edit&section=16" title="Modifier le code source de la section : Autres (en français)"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Gilles Dowek, <i>Les Métamorphoses du calcul</i>, Éditions <i>Le Pommier</i>, un ouvrage en français qui retrace l'histoire de la calculabilité et ses liens avec la déduction. <a href="/wiki/Prix_de_l%27Acad%C3%A9mie_fran%C3%A7aise#Philosophie" title="Prix de l'Académie française">Grand prix de philosophie de l'Académie Française</a></li></ul> <div class="navbox-container" style="clear:both;"> <table class="navbox collapsible noprint autocollapse" style=""> <tbody><tr><th class="navbox-title" colspan="2" style=""><div style="float:left; width:6em; text-align:left"><div class="noprint plainlinks nowrap tnavbar" style="padding:0; font-size:xx-small; color:var(--color-emphasized, #000000);"><a href="/wiki/Mod%C3%A8le:Palette_Informatique_th%C3%A9orique" title="Modèle:Palette Informatique théorique"><abbr class="abbr" title="Voir ce modèle.">v</abbr></a> · <a class="external text" href="https://fr.wikipedia.org/w/index.php?title=Mod%C3%A8le:Palette_Informatique_th%C3%A9orique&action=edit"><abbr class="abbr" title="Modifier ce modèle. Merci de prévisualiser avant de sauvegarder.">m</abbr></a></div></div><div style="font-size:110%"><a href="/wiki/Informatique_th%C3%A9orique" title="Informatique théorique">Informatique théorique</a></div></th> </tr> <tr> <th class="navbox-group" style="">Codage</th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Codage_de_l%27information" title="Codage de l'information">Codage de l'information</a></li> <li><a href="/wiki/Compression_de_donn%C3%A9es" title="Compression de données">Compression de données</a></li> <li><a href="/wiki/Chiffrement" title="Chiffrement">Chiffrement</a></li> <li><a href="/wiki/Cryptanalyse" title="Cryptanalyse">Cryptanalyse</a></li> <li><a href="/wiki/Cryptographie" title="Cryptographie">Cryptographie</a></li> <li><a href="/wiki/Th%C3%A9orie_de_l%27information" title="Théorie de l'information">Théorie de l'information</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Modèles de calcul</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Th%C3%A9orie_de_la_calculabilit%C3%A9" title="Théorie de la calculabilité">Calculabilité</a></li> <li><a href="/wiki/D%C3%A9cidabilit%C3%A9" title="Décidabilité">Décidabilité et indécidabilité</a></li> <li><a href="/wiki/Ensemble_r%C3%A9cursif" title="Ensemble récursif">Ensemble récursif</a></li> <li><a href="/wiki/Probl%C3%A8me_de_l%27arr%C3%AAt" title="Problème de l'arrêt">Problème de l'arrêt</a></li> <li><a href="/wiki/R%C3%A9cursivement_%C3%A9num%C3%A9rable" title="Récursivement énumérable">Ensemble récursivement énumérable</a></li> <li><a href="/wiki/Machine_de_Turing" title="Machine de Turing">Machine de Turing</a></li> <li><a class="mw-selflink selflink">Thèse de Church</a></li> <li><a href="/wiki/Automate_cellulaire" title="Automate cellulaire">Automate cellulaire</a></li> <li><a href="/wiki/R%C3%A9seau_de_neurones_artificiels" title="Réseau de neurones artificiels">Réseau de neurones artificiels</a></li> <li><a href="/wiki/R%C3%A9duction_polynomiale" title="Réduction polynomiale">Réduction polynomiale</a></li> <li><a href="/wiki/Cat%C3%A9gorie:Probl%C3%A8me_NP-complet" title="Catégorie:Problème NP-complet">Problème NP-complet</a></li> <li><a href="/wiki/Principe_de_Church-Turing-Deutsch" title="Principe de Church-Turing-Deutsch">Principe de Church-Turing-Deutsch</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Algorithmique" title="Algorithmique">Algorithmique</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Algorithmique" title="Algorithmique">Algorithmique</a></li> <li><a href="/wiki/Algorithme_glouton" title="Algorithme glouton">Algorithme glouton</a></li> <li><a href="/wiki/Algorithme_probabiliste" title="Algorithme probabiliste">Algorithme probabiliste</a></li> <li><a href="/wiki/Algorithme_g%C3%A9n%C3%A9tique" title="Algorithme génétique">Algorithme génétique</a></li> <li><a href="/wiki/Th%C3%A9orie_de_la_complexit%C3%A9_(informatique_th%C3%A9orique)" title="Théorie de la complexité (informatique théorique)">Complexité algorithmique</a></li> <li><a href="/wiki/Analyse_de_la_complexit%C3%A9_des_algorithmes" title="Analyse de la complexité des algorithmes">Analyse d'algorithme</a></li> <li><a href="/wiki/Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">Diviser pour régner</a></li> <li><a href="/wiki/Heuristique_(math%C3%A9matiques)" title="Heuristique (mathématiques)">Heuristique</a></li> <li><a href="/wiki/Programmation_dynamique" title="Programmation dynamique">Programmation dynamique</a></li> <li><a href="/wiki/G%C3%A9om%C3%A9trie_algorithmique" title="Géométrie algorithmique">Géométrie algorithmique</a></li> <li><a href="/wiki/Algorithme_de_tri" title="Algorithme de tri">Algorithmes de tri</a></li> <li><a href="/wiki/Algorithmique_du_texte" title="Algorithmique du texte">Algorithmique du texte</a></li> <li><a href="/wiki/Exploration_de_donn%C3%A9es" title="Exploration de données">Exploration de données</a></li> <li><a href="/wiki/Science_des_donn%C3%A9es" title="Science des données">Science des données</a></li> <li><a href="/wiki/Apprentissage_profond" title="Apprentissage profond">Apprentissage profond</a></li> <li><a href="/wiki/Test_de_primalit%C3%A9" title="Test de primalité">Test de primalité</a></li> <li><a href="/wiki/Structure_de_donn%C3%A9es" title="Structure de données">Structure de données</a></li> <li><a href="/wiki/Arbre_enracin%C3%A9" title="Arbre enraciné">Arbre enraciné</a></li> <li><a href="/wiki/Programmation_concurrente" title="Programmation concurrente">Concurrence</a></li> <li><a href="/wiki/Parall%C3%A9lisme_(informatique)" title="Parallélisme (informatique)">Parallélisme</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Syntaxe</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/R%C3%A9%C3%A9criture_(informatique)" title="Réécriture (informatique)">Réécriture</a></li> <li><a href="/wiki/Compilateur" title="Compilateur">Compilation</a></li> <li><a href="/wiki/Expression_r%C3%A9guli%C3%A8re" title="Expression régulière">Expression régulière</a></li> <li><a href="/wiki/Grammaire_formelle" title="Grammaire formelle">Grammaire formelle</a></li> <li><a href="/wiki/Langage_rationnel" title="Langage rationnel">Langage rationnel</a></li> <li><a href="/wiki/Ensemble_rationnel" title="Ensemble rationnel">Ensemble rationnel</a></li> <li><a href="/wiki/Langage_formel" title="Langage formel">Théorie des langages</a></li> <li><a href="/wiki/Th%C3%A9orie_des_automates" title="Théorie des automates">Théorie des automates</a></li> <li><a href="/wiki/Automate_fini" title="Automate fini">Automate fini</a></li> <li><a href="/wiki/Automate_sur_les_mots_infinis" title="Automate sur les mots infinis">Automate sur les mots infinis</a></li> <li><a href="/wiki/Automate_d%27arbres" title="Automate d'arbres">Automate d'arbres</a></li> <li><a href="/wiki/Automate_%C3%A0_pile" title="Automate à pile">Automate à pile</a></li> <li><a href="/wiki/Hi%C3%A9rarchie_de_Chomsky" title="Hiérarchie de Chomsky">Hiérarchie de Chomsky</a></li> <li><a href="/wiki/Linguistique_informatique" title="Linguistique informatique">Linguistique informatique</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style="">Sémantique</th> <td class="navbox-list navbox-even" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Interpr%C3%A9tation_abstraite" title="Interprétation abstraite">Interprétation abstraite</a></li> <li><a href="/wiki/M%C3%A9thode_formelle_(informatique)" title="Méthode formelle (informatique)">Méthodes formelles</a></li> <li><a href="/wiki/V%C3%A9rification_de_mod%C3%A8les" title="Vérification de modèles">Vérification de modèles</a></li> <li><a href="/wiki/S%C3%A9mantique_des_langages_de_programmation" title="Sémantique des langages de programmation">Sémantique des langages de programmation</a></li> <li><a href="/wiki/S%C3%A9mantique_d%C3%A9notationnelle" title="Sémantique dénotationnelle">Sémantique dénotationnelle</a></li> <li><a href="/wiki/S%C3%A9mantique_axiomatique" title="Sémantique axiomatique">Sémantique axiomatique</a></li> <li><a href="/wiki/S%C3%A9mantique_op%C3%A9rationnelle" title="Sémantique opérationnelle">Sémantique opérationnelle</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Logique_math%C3%A9matique" title="Logique mathématique">Logique mathématique</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Assistant_de_preuve" title="Assistant de preuve">Assistant de preuve</a></li> <li><a href="/wiki/Calcul_des_pr%C3%A9dicats" title="Calcul des prédicats">Calcul des prédicats</a></li> <li><a href="/wiki/Correspondance_de_Curry-Howard" title="Correspondance de Curry-Howard">Correspondance de Curry-Howard</a></li> <li><a href="/wiki/Fonction_r%C3%A9cursive" title="Fonction récursive">Fonction récursive</a></li> <li><a href="/wiki/Lambda-calcul" title="Lambda-calcul">Lambda-calcul</a></li> <li><a href="/wiki/Th%C3%A9or%C3%A8mes_d%27incompl%C3%A9tude_de_G%C3%B6del" title="Théorèmes d'incomplétude de Gödel">Théorèmes d'incomplétude de Gödel</a></li> <li><a href="/wiki/Th%C3%A9orie_des_types" title="Théorie des types">Théorie des types</a></li></ul> </div></td> </tr> <tr> <th class="navbox-group" style=""><a href="/wiki/Math%C3%A9matiques_discr%C3%A8tes" title="Mathématiques discrètes">Mathématiques discrètes</a></th> <td class="navbox-list" style=""><div class="liste-horizontale"> <ul><li><a href="/wiki/Combinatoire" title="Combinatoire">Combinatoire</a></li> <li><a href="/wiki/Algorithme_du_simplexe" title="Algorithme du simplexe">Algorithme du simplexe</a></li> <li><a href="/wiki/Optimisation_combinatoire" title="Optimisation combinatoire">Optimisation combinatoire</a></li> <li><a href="/wiki/Th%C3%A9orie_des_graphes" title="Théorie des graphes">Théorie des graphes</a></li> <li><a href="/wiki/Liste_des_algorithmes_de_la_th%C3%A9orie_des_graphes" title="Liste des algorithmes de la théorie des graphes">Algorithmes de la théorie des graphes</a></li> <li><a href="/wiki/Recherche_op%C3%A9rationnelle" title="Recherche opérationnelle">Recherche opérationnelle</a></li> <li><a href="/wiki/Th%C3%A9orie_de_la_d%C3%A9cision" title="Théorie de la décision">Théorie de la décision</a></li> <li><a href="/wiki/Analyse_num%C3%A9rique" title="Analyse numérique">Analyse numérique</a></li></ul> </div></td> </tr> </tbody></table> </div> <ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Thèse_de_Church&oldid=220522668">https://fr.wikipedia.org/w/index.php?title=Thèse_de_Church&oldid=220522668</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:Intelligence_artificielle" title="Catégorie:Intelligence artificielle">Intelligence artificielle</a></li><li><a href="/wiki/Cat%C3%A9gorie:Calculabilit%C3%A9" title="Catégorie:Calculabilité">Calculabilité</a></li><li><a href="/wiki/Cat%C3%A9gorie:Alan_Turing" title="Catégorie:Alan Turing">Alan Turing</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> La dernière modification de cette page a été faite le 22 novembre 2024 à 20:54.</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%A8se_de_Church" title="Spécial:Citer/Thèse de Church">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%A8se_de_Church&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-78f4c97c5d-vk7xj","wgBackendResponseTime":157,"wgPageParseReport":{"limitreport":{"cputime":"0.331","walltime":"0.476","ppvisitednodes":{"value":2708,"limit":1000000},"postexpandincludesize":{"value":94668,"limit":2097152},"templateargumentsize":{"value":16736,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":22215,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 359.891 1 -total"," 26.95% 96.997 3 Modèle:Références"," 14.18% 51.047 1 Modèle:Portail"," 11.45% 41.215 15 Modèle:Article"," 11.34% 40.822 4 Modèle:Ouvrage"," 10.78% 38.787 1 Modèle:Les_métamorphoses_du_calcul"," 8.57% 30.840 5 Modèle:Lang"," 7.86% 28.301 1 Modèle:Voir_homonyme"," 7.30% 26.276 1 Modèle:Méta_bandeau_de_note"," 6.69% 24.073 1 Modèle:Catégorisation_badges"]},"scribunto":{"limitreport-timeusage":{"value":"0.125","limit":"10.000"},"limitreport-memusage":{"value":5600236,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-b9b867ddb-m5q4z","timestamp":"20241128092703","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Th\u00e8se de Church","url":"https:\/\/fr.wikipedia.org\/wiki\/Th%C3%A8se_de_Church","sameAs":"http:\/\/www.wikidata.org\/entity\/Q309157","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q309157","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-03-16T06:06:28Z","dateModified":"2024-11-22T19:54:41Z","headline":"th\u00e8se sur les mod\u00e8les de calculs statuant qu'il n'existe pas de mod\u00e8le de calcul plus puissant que la machine de Turing"}</script> </body> </html>