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="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Turing degree - Wikipedia</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(/(?:^|; )enwikimwclientpreferences=([^;]+)/);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":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"dc7d1e6f-37a4-425c-9a89-190a827692fb","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Turing_degree","wgTitle":"Turing degree","wgCurRevisionId":1247797080,"wgRevisionId":1247797080,"wgArticleId":764405,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Computability theory","Theory of computation","Alan Turing"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Turing_degree","wgRelevantArticleId":764405,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false, "wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1527413","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"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","ext.scribunto.logs","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","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=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.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=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&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="Turing degree - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Turing_degree"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Turing_degree&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="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Turing_degree"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&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-Turing_degree rootpage-Turing_degree skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</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="Main menu" > <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">Main menu</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">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</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/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" 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="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; 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/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</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="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <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="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <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="Appearance" > <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">Appearance</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="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</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=Special:CreateAccount&returnto=Turing+degree" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</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=Special:UserLogin&returnto=Turing+degree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</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="Log in and more 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="Personal tools" > <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">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <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="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Turing+degree" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Turing+degree" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</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 for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</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/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</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="Contents" 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">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</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">(Top)</div> </a> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Overview</span> </div> </a> <ul id="toc-Overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Turing_equivalence" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Turing_equivalence"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Turing equivalence</span> </div> </a> <ul id="toc-Turing_equivalence-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Basic_properties_of_the_Turing_degrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Basic_properties_of_the_Turing_degrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Basic properties of the Turing degrees</span> </div> </a> <ul id="toc-Basic_properties_of_the_Turing_degrees-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Structure_of_the_Turing_degrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Structure_of_the_Turing_degrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Structure of the Turing degrees</span> </div> </a> <button aria-controls="toc-Structure_of_the_Turing_degrees-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>Toggle Structure of the Turing degrees subsection</span> </button> <ul id="toc-Structure_of_the_Turing_degrees-sublist" class="vector-toc-list"> <li id="toc-Order_properties" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Order_properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Order properties</span> </div> </a> <ul id="toc-Order_properties-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Properties_involving_the_jump" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Properties_involving_the_jump"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Properties involving the jump</span> </div> </a> <ul id="toc-Properties_involving_the_jump-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Logical_properties" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Logical_properties"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Logical properties</span> </div> </a> <ul id="toc-Logical_properties-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Recursively_enumerable_Turing_degrees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Recursively_enumerable_Turing_degrees"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Recursively enumerable Turing degrees</span> </div> </a> <ul id="toc-Recursively_enumerable_Turing_degrees-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Post's_problem_and_the_priority_method" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Post's_problem_and_the_priority_method"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Post's problem and the priority method</span> </div> </a> <ul id="toc-Post's_problem_and_the_priority_method-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <button aria-controls="toc-References-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>Toggle References subsection</span> </button> <ul id="toc-References-sublist" class="vector-toc-list"> <li id="toc-Monographs_(undergraduate_level)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Monographs_(undergraduate_level)"> <div class="vector-toc-text"> <span class="vector-toc-numb">8.1</span> <span>Monographs (undergraduate level)</span> </div> </a> <ul id="toc-Monographs_(undergraduate_level)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Monographs_and_survey_articles_(graduate_level)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Monographs_and_survey_articles_(graduate_level)"> <div class="vector-toc-text"> <span class="vector-toc-numb">8.2</span> <span>Monographs and survey articles (graduate level)</span> </div> </a> <ul id="toc-Monographs_and_survey_articles_(graduate_level)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Research_papers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Research_papers"> <div class="vector-toc-text"> <span class="vector-toc-numb">8.3</span> <span>Research papers</span> </div> </a> <ul id="toc-Research_papers-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </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="Contents" 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="Toggle the table of contents" > <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">Toggle the table of contents</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">Turing degree</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="Go to an article in another language. Available in 8 languages" > <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-8" 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">8 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BF%D0%B5%D0%BD_%D0%BD%D0%B0_%D0%A2%D1%8E%D1%80%D0%B8%D0%BD%D0%B3" title="Степен на Тюринг – Bulgarian" lang="bg" hreflang="bg" data-title="Степен на Тюринг" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Turinggrad" title="Turinggrad – German" lang="de" hreflang="de" data-title="Turinggrad" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Degr%C3%A9_de_Turing" title="Degré de Turing – French" lang="fr" hreflang="fr" data-title="Degré de Turing" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Grado_di_Turing" title="Grado di Turing – Ido" lang="io" hreflang="io" data-title="Grado di Turing" data-language-autonym="Ido" data-language-local-name="Ido" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%AC%A1%E6%95%B0" title="チューリング次数 – Japanese" lang="ja" hreflang="ja" data-title="チューリング次数" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Grau_de_Turing" title="Grau de Turing – Portuguese" lang="pt" hreflang="pt" data-title="Grau de Turing" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BF%D1%96%D0%BD%D1%8C_%D0%A2%D1%8E%D1%80%D1%96%D0%BD%D0%B3%D0%B0" title="Степінь Тюрінга – Ukrainian" lang="uk" hreflang="uk" data-title="Степінь Тюрінга" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8F%AF%E8%A7%A3%E5%BA%A6" title="不可解度 – Chinese" lang="zh" hreflang="zh" data-title="不可解度" data-language-autonym="中文" data-language-local-name="Chinese" 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/Q1527413#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</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="Namespaces"> <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/Turing_degree" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Turing_degree" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</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="Change language variant" > <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">English</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="Views"> <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/Turing_degree"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Turing_degree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Turing_degree&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <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="Tools" > <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">Tools</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">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More 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/Turing_degree"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Turing_degree&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Turing_degree&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Turing_degree" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Turing_degree" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Turing_degree&oldid=1247797080" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Turing_degree&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Turing_degree&id=1247797080&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTuring_degree"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTuring_degree"><span>Download QR code</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"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Turing_degree&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Turing_degree&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</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"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1527413" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</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="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <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">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</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">From Wikipedia, the free encyclopedia</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="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Measure of unsolvability</div> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a> and <a href="/wiki/Mathematical_logic" title="Mathematical logic">mathematical logic</a> the <b>Turing degree</b> (named after <a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a>) or <b>degree of unsolvability</b> of a set of <a href="/wiki/Natural_number" title="Natural number">natural numbers</a> measures the level of algorithmic unsolvability of the set. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The concept of Turing degree is fundamental in <a href="/wiki/Computability_theory" title="Computability theory">computability theory</a>, where sets of natural numbers are often regarded as <a href="/wiki/Decision_problem" title="Decision problem">decision problems</a>. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. </p><p>Two sets are <b>Turing equivalent</b> if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are <a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partially ordered</a>, so that if the Turing degree of a set <i>X</i> is less than the Turing degree of a set <i>Y</i>, then any (possibly noncomputable) procedure that correctly decides whether numbers are in <i>Y</i> can be effectively converted to a procedure that correctly decides whether numbers are in <i>X</i>. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability. </p><p>The Turing degrees were introduced by <a href="#CITEREFPost1944">Post (1944)</a> and many fundamental results were established by <a href="#CITEREFKleenePost1954">Kleene & Post (1954)</a>. The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the <b>priority method</b>. </p> <div class="mw-heading mw-heading2"><h2 id="Turing_equivalence">Turing equivalence</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=2" title="Edit section: Turing equivalence"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Turing_reduction" title="Turing reduction">Turing reduction</a></div> <p>For the rest of this article, the word <i>set</i> will refer to a set of natural numbers. A set <i>X</i> is said to be <b><a href="/wiki/Turing_reducible" class="mw-redirect" title="Turing reducible">Turing reducible</a></b> to a set <i>Y</i> if there is an <a href="/wiki/Oracle_Turing_machine" class="mw-redirect" title="Oracle Turing machine">oracle Turing machine</a> that decides membership in <i>X</i> when given an oracle for membership in <i>Y</i>. The notation <i>X</i> ≤<sub>T</sub> <i>Y</i> indicates that <i>X</i> is Turing reducible to <i>Y</i>. </p><p>Two sets <i>X</i> and <i>Y</i> are defined to be <b>Turing equivalent</b> if <i>X</i> is Turing reducible to <i>Y</i> and <i>Y</i> is Turing reducible to <i>X</i>. The notation <i>X</i> ≡<sub>T</sub> <i>Y</i> indicates that <i>X</i> and <i>Y</i> are Turing equivalent. The relation ≡<sub>T</sub> can be seen to be an <a href="/wiki/Equivalence_relation" title="Equivalence relation">equivalence relation</a>, which means that for all sets <i>X</i>, <i>Y</i>, and <i>Z</i>: </p> <ul><li><i>X</i> ≡<sub>T</sub> <i>X</i></li> <li><i>X</i> ≡<sub>T</sub> <i>Y</i> implies <i>Y</i> ≡<sub>T</sub> <i>X</i></li> <li>If <i>X</i> ≡<sub>T</sub> <i>Y</i> and <i>Y</i> ≡<sub>T</sub> <i>Z</i> then <i>X</i> ≡<sub>T</sub> <i>Z</i>.</li></ul> <p>A <b>Turing degree</b> is an <a href="/wiki/Equivalence_class" title="Equivalence class">equivalence class</a> of the relation ≡<sub>T</sub>. The notation [<i>X</i>] denotes the equivalence class containing a set <i>X</i>. The entire collection of Turing degrees is denoted <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span>. </p><p>The Turing degrees have a <a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partial order</a> ≤ defined so that [<i>X</i>] ≤ [<i>Y</i>] if and only if <i>X</i> ≤<sub>T</sub> <i>Y</i>. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted <b>0</b> (zero) because it is the least element of the poset <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span>. (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with [<i>X</i>], the boldface is not necessary.) </p><p>For any sets <i>X</i> and <i>Y</i>, X <b>join</b> Y, written <i>X</i> ⊕ <i>Y</i>, is defined to be the union of the sets <span class="nowrap">{2<i>n</i> : <i>n</i> ∈ <i>X</i></span>} and <span class="nowrap">{2<i>m</i>+1 : <i>m</i> ∈ <i>Y</i></span>}. The Turing degree of <i>X</i> ⊕ <i>Y</i> is the <a href="/wiki/Join_(mathematics)" class="mw-redirect" title="Join (mathematics)">least upper bound</a> of the degrees of <i>X</i> and <i>Y</i>. Thus <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> is a <a href="/wiki/Join-semilattice" class="mw-redirect" title="Join-semilattice">join-semilattice</a>. The least upper bound of degrees <b>a</b> and <b>b</b> is denoted <b>a</b> ∪ <b>b</b>. It is known that <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> is not a <a href="/wiki/Lattice_(order)" title="Lattice (order)">lattice</a>, as there are pairs of degrees with no greatest lower bound. </p><p>For any set <i>X</i> the notation <i>X</i>′ denotes the set of indices of oracle machines that halt (when given their index as input) when using <i>X</i> as an oracle. The set <i>X</i>′ is called the <b><a href="/wiki/Turing_jump" title="Turing jump">Turing jump</a></b> of <i>X</i>. The Turing jump of a degree [<i>X</i>] is defined to be the degree [<i>X</i>′]; this is a valid definition because <i>X</i>′ ≡<sub>T</sub> <i>Y</i>′ whenever <i>X</i> ≡<sub>T</sub> <i>Y</i>. A key example is <b>0</b>′, the degree of the <a href="/wiki/Halting_problem" title="Halting problem">halting problem</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Basic_properties_of_the_Turing_degrees">Basic properties of the Turing degrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=3" title="Edit section: Basic properties of the Turing degrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Every Turing degree is <a href="/wiki/Countably_infinite" class="mw-redirect" title="Countably infinite">countably infinite</a>, that is, it contains exactly <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 \aleph _{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi mathvariant="normal">ℵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \aleph _{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/721cd7f8c15a2e72ad162bdfa5baea8eef98aab1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle \aleph _{0}}"></span> sets.</li> <li>There are <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^{\aleph _{0}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi mathvariant="normal">ℵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{\aleph _{0}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/779da5db4ed54fa334dd92089cdf1c284e45febb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.231ex; height:2.676ex;" alt="{\displaystyle 2^{\aleph _{0}}}"></span> distinct Turing degrees.</li> <li>For each degree <b>a</b> the strict inequality <b>a</b> < <b>a</b>′ holds.</li> <li>For each degree <b>a</b>, the set of degrees below <b>a</b> is <a href="/wiki/Countable_set" title="Countable set">countable</a>. The set of degrees greater than <b>a</b> has size <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^{\aleph _{0}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi mathvariant="normal">ℵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{\aleph _{0}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/779da5db4ed54fa334dd92089cdf1c284e45febb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.231ex; height:2.676ex;" alt="{\displaystyle 2^{\aleph _{0}}}"></span>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Structure_of_the_Turing_degrees">Structure of the Turing degrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=4" title="Edit section: Structure of the Turing degrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A great deal of research has been conducted into the structure of the Turing degrees. The following survey lists only some of the many known results. One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated. </p> <div class="mw-heading mw-heading3"><h3 id="Order_properties">Order properties</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=5" title="Edit section: Order properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>There are <b>minimal degrees</b>. A degree <b>a</b> is <i>minimal</i> if <b>a</b> is nonzero and there is no degree between <b>0</b> and <b>a</b>. Thus the order relation on the degrees is not a <a href="/wiki/Dense_order" title="Dense order">dense order</a>.</li> <li>The Turing degrees are not linearly ordered by ≤<sub>T</sub>.<sup id="cite_ref-FOOTNOTEDeAntonio20109_1-0" class="reference"><a href="#cite_note-FOOTNOTEDeAntonio20109-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li> <li>In fact, for every nonzero degree <b>a</b> there is a degree <b>b</b> incomparable with <b>a</b>.</li> <li>There is a set of <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^{\aleph _{0}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi mathvariant="normal">ℵ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{\aleph _{0}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/779da5db4ed54fa334dd92089cdf1c284e45febb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.231ex; height:2.676ex;" alt="{\displaystyle 2^{\aleph _{0}}}"></span> pairwise incomparable Turing degrees.</li> <li>There are pairs of degrees with no greatest lower bound. Thus <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> is not a <a href="/wiki/Lattice_(order)" title="Lattice (order)">lattice</a>.</li> <li>Every countable partially ordered set can be embedded in the Turing degrees.</li> <li>An infinite strictly increasing sequence <b>a</b><sub>1</sub>, <b>a</b><sub>2</sub>, ... of Turing degrees cannot have a least upper bound, but it always has an <i>exact pair</i> <b>c</b>, <b>d</b> such that ∀<b>e</b> (<b>e</b><<b>c</b>∧<b>e</b><<b>d</b> ⇔ ∃<i>i</i> <b>e</b>≤<b>a</b><sub><i>i</i></sub>), and thus it has (non-unique) minimal upper bounds.</li> <li>Assuming the <a href="/wiki/Axiom_of_constructibility" title="Axiom of constructibility">axiom of constructibility</a>, it can be shown there is a maximal chain of degrees of order type <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 \omega _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e20e29ac56d6cc52eaeb2f9c0bf79ef706428ddf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.5ex; height:2.009ex;" alt="{\displaystyle \omega _{1}}"></span>.<sup id="cite_ref-FOOTNOTEChongYu20071224_2-0" class="reference"><a href="#cite_note-FOOTNOTEChongYu20071224-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li></ul> <div class="mw-heading mw-heading3"><h3 id="Properties_involving_the_jump">Properties involving the jump</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=6" title="Edit section: Properties involving the jump"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>For every degree <b>a</b> there is a degree strictly between <b>a</b> and <b>a′</b>. In fact, there is a countable family of pairwise incomparable degrees between <b>a</b> and <b>a′</b>.</li> <li>Jump inversion: a degree <b>a</b> is of the form <b>b′</b> if and only if <b>0′</b> ≤ <b>a</b>.</li> <li>For any degree <b>a</b> there is a degree <b>b</b> such that <b>a</b> < <b>b</b> and <b>b′</b> = <b>a′</b>; such a degree <b>b</b> is called <i>low</i> relative to <b>a</b>.</li> <li>There is an infinite sequence <b>a</b><sub><i>i</i></sub> of degrees such that <b>a</b>′<sub><i>i</i>+1</sub> ≤ <b>a</b><sub><i>i</i></sub> for each <i>i</i>.</li> <li><a href="/wiki/Post%27s_theorem" title="Post's theorem">Post's theorem</a> establishes a close correspondence between the <a href="/wiki/Arithmetical_hierarchy" title="Arithmetical hierarchy">arithmetical hierarchy</a> and finitely iterated Turing jumps of the empty set.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Logical_properties">Logical properties</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=7" title="Edit section: Logical properties"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="#CITEREFSimpson1977b">Simpson (1977b)</a> showed that the <a href="/wiki/First-order_theory" class="mw-redirect" title="First-order theory">first-order theory</a> of <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> in the language <span class="nowrap">⟨ ≤, = ⟩</span> or <span class="nowrap">⟨ ≤, ′, = ⟩</span> is <a href="/wiki/Many-one_reduction" title="Many-one reduction">many-one equivalent</a> to the theory of <a href="/wiki/True_arithmetic#True_theory_of_second-order_arithmetic" title="True arithmetic">true second-order arithmetic</a>. This indicates that the structure of <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> is extremely complicated.</li> <li><a href="#CITEREFShoreSlaman1999">Shore & Slaman (1999)</a> showed that the jump operator is definable in the first-order structure of <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 {\mathcal {D}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">D</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3277962e1959c3241fb1b70c7f0ac6dcefebd966" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.792ex; height:2.176ex;" alt="{\displaystyle {\mathcal {D}}}"></span> with the language <span class="nowrap">⟨ ≤, = ⟩</span>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Recursively_enumerable_Turing_degrees">Recursively enumerable Turing degrees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=8" title="Edit section: Recursively enumerable Turing degrees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Frame"><a href="/wiki/File:Rehasse.png" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/e/ea/Rehasse.png" decoding="async" width="78" height="141" class="mw-file-element" data-file-width="78" data-file-height="141" /></a><figcaption>A finite lattice that can't be embedded in the r.e. degrees.</figcaption></figure> <p>A degree is called <i>recursively enumerable</i> (r.e.) or <i>computably enumerable</i> (c.e.) if it contains a <a href="/wiki/Recursively_enumerable_set" class="mw-redirect" title="Recursively enumerable set">recursively enumerable set</a>. Every r.e. degree is below <b>0′</b>, but not every degree below <b>0′</b> is r.e.. However, a set <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 A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></span> is many-one reducible to <b>0′</b> iff <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 A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></span> is r.e..<sup id="cite_ref-FOOTNOTEOdifreddi1989252,_258_3-0" class="reference"><a href="#cite_note-FOOTNOTEOdifreddi1989252,_258-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <ul><li><a href="#CITEREFSacks1964">Sacks (1964)</a>: The r.e. degrees are dense; between any two r.e. degrees there is a third r.e. degree.</li> <li><a href="#CITEREFLachlan1966a">Lachlan (1966a)</a> and <a href="#CITEREFYates1966">Yates (1966)</a>: There are two r.e. degrees with no greatest lower bound in the r.e. degrees.</li> <li><a href="#CITEREFLachlan1966a">Lachlan (1966a)</a> and <a href="#CITEREFYates1966">Yates (1966)</a>: There is a pair of nonzero r.e. degrees whose greatest lower bound is <b>0</b>.</li> <li><a href="#CITEREFLachlan1966b">Lachlan (1966b)</a>: There is no pair of r.e. degrees whose greatest lower bound is <b>0</b> and whose least upper bound is <b>0′</b>. This result is informally called the <i>nondiamond theorem</i>.</li> <li><a href="#CITEREFThomason1971">Thomason (1971)</a>: Every finite <a href="/wiki/Distributive_lattice" title="Distributive lattice">distributive lattice</a> can be embedded into the r.e. degrees. In fact, the countable <a href="/wiki/Atom_(order_theory)" title="Atom (order theory)">atomless</a> <a href="/wiki/Boolean_algebra" title="Boolean algebra">Boolean algebra</a> can be embedded in a manner that preserves <a href="/wiki/Infimum_and_supremum" title="Infimum and supremum">suprema and infima</a>.</li> <li><a href="#CITEREFLachlanSoare1980">Lachlan & Soare (1980)</a>: Not all finite <a href="/wiki/Lattice_(order)" title="Lattice (order)">lattices</a> can be embedded in the r.e. degrees (via an embedding that preserves suprema and infima). A particular example is shown to the right. <a href="/wiki/Leo_Harrington" title="Leo Harrington">L. A. Harrington</a> and <a href="/wiki/Theodore_Slaman" title="Theodore Slaman">T. A. Slaman</a> (see <a href="#CITEREFNiesShoreSlaman1998">Nies, Shore & Slaman (1998)</a>): The first-order theory of the r.e. degrees in the language ⟨ <b>0</b>, ≤, = ⟩ is many-one equivalent to the theory of <a href="/wiki/True_arithmetic" title="True arithmetic">true first-order arithmetic</a>.</li></ul> <p>Additionally, there is Shoenfield's limit lemma, a set A satisfies <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 [A]\leq _{T}\emptyset '}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">[</mo> <mi>A</mi> <mo stretchy="false">]</mo> <msub> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> <msup> <mi mathvariant="normal">∅</mi> <mo>′</mo> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle [A]\leq _{T}\emptyset '}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/241460e7eed374f2275c14404cfbf97d6180c7ff" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.372ex; height:3.009ex;" alt="{\displaystyle [A]\leq _{T}\emptyset '}"></span> iff there is a "recursive approximation" to its characteristic function: a function <i>g</i> such that for sufficiently large <i>s</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(s)=\chi _{A}(s)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>χ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>A</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(s)=\chi _{A}(s)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f0575a822b4542e7420fc5035d4a4767c9cc26d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.934ex; height:2.843ex;" alt="{\displaystyle g(s)=\chi _{A}(s)}"></span>.<sup id="cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-0" class="reference"><a href="#cite_note-FOOTNOTEEpsteinHaasKramer1981-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>A set <i>A</i> is called <i>n</i>-r e. if there is a family of functions <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 (A_{s})_{s\in \mathbb {N} }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> </mrow> </msub> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (A_{s})_{s\in \mathbb {N} }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2a27e86dceed82b60b1c164ab7bc6c1b74e3cfd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.842ex; height:2.843ex;" alt="{\displaystyle (A_{s})_{s\in \mathbb {N} }}"></span> such that:<sup id="cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-1" class="reference"><a href="#cite_note-FOOTNOTEEpsteinHaasKramer1981-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <ul><li><i>A</i><sub>s</sub> is a recursive approximation of <i>A</i>: for some <i>t</i>, for any <i>s</i>≥<i>t</i> we have <i>A</i><sub><i>s</i></sub>(<i>x</i>) = <i>A</i>(<i>x</i>), in particular conflating <i>A</i> with its characteristic function. <i>(Removing this condition yields a definition of</i> A <i>being</i> "weakly <i>n</i>-r.e."<i>)</i></li> <li><i>A</i><sub>s</sub> is an "<i>n</i>-trial predicate": for all <i>x</i>, <i>A</i><sub>0</sub>(<i>x</i>)=0 and the cardinality of <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 \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>s</mi> <mo>∣</mo> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>≠</mo> <msub> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>s</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0db0ebfa60b25034375fd7d04c71cc2bf5cd26f9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.322ex; height:2.843ex;" alt="{\displaystyle \{s\mid A_{s}(x)\neq A_{s+1}(x)\}}"></span> is ≤n.</li></ul> <p>Properties of <i>n</i>-r.e. degrees:<sup id="cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-2" class="reference"><a href="#cite_note-FOOTNOTEEpsteinHaasKramer1981-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <ul><li>The class of sets of <i>n</i>-r.e. degree is a strict subclass of the class of sets of (<i>n</i>+1)-r.e. degree.</li> <li>For all <i>n</i>>1 there are two (<i>n</i>+1)-r.e. degrees <b>a</b>, <b>b</b> with <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 \mathbf {a} \leq _{T}\mathbf {b} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">a</mi> </mrow> <msub> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">b</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/507909f434a0660b1ae95b5fd12b2f00837577b2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.273ex; height:2.509ex;" alt="{\displaystyle \mathbf {a} \leq _{T}\mathbf {b} }"></span>, such that the segment <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 \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">c</mi> </mrow> <mo>∣</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">a</mi> </mrow> <msub> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">c</mi> </mrow> <msub> <mo>≤</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>T</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">b</mi> </mrow> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c1b85995422971efddfbddf528be1f63448aa265" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.398ex; height:2.843ex;" alt="{\displaystyle \{\mathbf {c} \mid \mathbf {a} \leq _{T}\mathbf {c} \leq _{T}\mathbf {b} \}}"></span> contains no <i>n</i>-r.e. degrees.</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}"></span> and <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 {\overline {A}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>A</mi> <mo accent="false">¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\overline {A}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92efef0e89bdc77f6a848764195ef5b9d9bfcc6a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.858ex; height:3.009ex;" alt="{\displaystyle {\overline {A}}}"></span> are (<i>n</i>+1)-r.e. iff both sets are weakly-<i>n</i>-r.e.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Post's_problem_and_the_priority_method"><span id="Post.27s_problem_and_the_priority_method"></span>Post's problem and the priority method</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=9" title="Edit section: Post's problem and the priority method"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"Post's problem" redirects here. For the other "Post's problem", see <a href="/wiki/Post%27s_correspondence_problem" class="mw-redirect" title="Post's correspondence problem">Post's correspondence problem</a>.</div> <p><a href="/wiki/Emil_Post" class="mw-redirect" title="Emil Post">Emil Post</a> studied the r.e. Turing degrees and asked whether there is any r.e. degree strictly between <b>0</b> and <b>0′</b>. The problem of constructing such a degree (or showing that none exist) became known as <b>Post's problem</b>. This problem was solved independently by <a href="/wiki/Richard_M._Friedberg" title="Richard M. Friedberg">Friedberg</a> and <a href="/wiki/Albert_Muchnik" title="Albert Muchnik">Muchnik</a> in the 1950s, who showed that these intermediate r.e. degrees do exist (<a href="/wiki/Friedberg%E2%80%93Muchnik_theorem" title="Friedberg–Muchnik theorem">Friedberg–Muchnik theorem</a>). Their proofs each developed the same new method for constructing r.e. degrees, which came to be known as the <b>priority method</b>. The priority method is now the main technique for establishing results about r.e. sets. </p><p>The idea of the priority method for constructing a r.e. set <i>X</i> is to list a countable sequence of <i>requirements</i> that <i>X</i> must satisfy. For example, to construct a r.e. set <i>X</i> between <b>0</b> and <b>0′</b> it is enough to satisfy the requirements <i>A<sub>e</sub></i> and <i>B<sub>e</sub></i> for each natural number <i>e</i>, where <i>A<sub>e</sub></i> requires that the oracle machine with index <i>e</i> does not compute 0′ from <i>X</i> and <i>B<sub>e</sub></i> requires that the Turing machine with index <i>e</i> (and no oracle) does not compute <i>X</i>. These requirements are put into a <i>priority ordering</i>, which is an explicit bijection of the requirements and the natural numbers. The proof proceeds inductively with one stage for each natural number; these stages can be thought of as steps of time during which the set <i>X</i> is enumerated. At each stage, numbers may be put into <i>X</i> or forever (if not injured) prevented from entering <i>X</i> in an attempt to <i>satisfy</i> requirements (that is, force them to hold once all of <i>X</i> has been enumerated). Sometimes, a number can be enumerated into <i>X</i> to satisfy one requirement but doing this would cause a previously satisfied requirement to become unsatisfied (that is, to be <i>injured</i>). The priority order on requirements is used to determine which requirement to satisfy in this case. The informal idea is that if a requirement is injured then it will eventually stop being injured after all higher priority requirements have stopped being injured, although not every priority argument has this property. An argument must be made that the overall set <i>X</i> is r.e. and satisfies all the requirements. Priority arguments can be used to prove many facts about r.e. sets; the requirements used and the manner in which they are satisfied must be carefully chosen to produce the required result. </p><p>For example, a <a href="/wiki/Simple_set" title="Simple set">simple</a> (and hence noncomputable r.e.) <a href="/wiki/Low_(computability)" title="Low (computability)">low</a> <i>X</i> (low means <i>X</i>′=0′) can be constructed in infinitely many stages as follows. At the start of stage <i>n</i>, let <i>T</i><sub><i>n</i></sub> be the output (binary) tape, identified with the set of cell indices where we placed 1 so far (so <i>X</i>=∪<sub><i>n</i></sub> <i>T</i><sub><i>n</i></sub>; <i>T</i><sub>0</sub>=∅); and let <i>P</i><sub><i>n</i></sub>(<i>m</i>) be the priority for not outputting 1 at location <i>m</i>; <i>P</i><sub>0</sub>(<i>m</i>)=∞. At stage <i>n</i>, if possible (otherwise do nothing in the stage), pick the least <i>i</i><<i>n</i> such that ∀<i>m</i> <i>P</i><sub><i>n</i></sub>(<i>m</i>)≠<i>i</i> and Turing machine <i>i</i> halts in <<i>n</i> steps on some input <i>S</i>⊇<i>T</i><sub><i>n</i></sub> with ∀<i>m</i>∈<i>S</i>\<i>T</i><sub><i>n</i></sub> <i>P</i><sub><i>n</i></sub>(<i>m</i>)≥<i>i</i>. Choose any such (finite) <i>S</i>, set <i>T</i><sub><i>n</i>+1</sub>=<i>S</i>, and for every cell <i>m</i> visited by machine <i>i</i> on <i>S</i>, set <i>P</i><sub><i>n</i>+1</sub>(<i>m</i>) = min(<i>i</i>, <i>P</i><sub><i>n</i></sub>(<i>m</i>)), and set all priorities ><i>i</i> to ∞, and then set one priority ∞ cell (any will do) not in <i>S</i> to priority <i>i</i>. Essentially, we make machine <i>i</i> halt if we can do so without upsetting priorities <<i>i</i>, and then set priorities to prevent machines ><i>i</i> from disrupting the halt; all priorities are eventually constant. </p><p>To see that <i>X</i> is low, machine <i>i</i> halts on <i>X</i> iff it halts in <<i>n</i> steps on some <i>T</i><sub><i>n</i></sub> such that machines <<i>i</i> that halt on <i>X</i> do so <<i>n</i>-<i>i</i> steps (by recursion, this is uniformly computable from 0′). <i>X</i> is noncomputable since otherwise a Turing machine could halt on <i>Y</i> iff <i>Y</i>\<i>X</i> is nonempty, contradicting the construction since <i>X</i> excludes some priority <i>i</i> cells for arbitrarily large <i>i</i>; and <i>X</i> is simple because for each <i>i</i> the number of priority <i>i</i> cells is finite. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=10" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Martin_measure" title="Martin measure">Martin measure</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=11" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Monographs_(undergraduate_level)"><span id="Monographs_.28undergraduate_level.29"></span>Monographs (undergraduate level)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=12" title="Edit section: Monographs (undergraduate level)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFCooper2004" class="citation book cs1">Cooper, S.B. (2004). <i>Computability theory</i>. Boca Raton, FL: Chapman & Hall/CRC. p. 424. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/1-58488-237-9" title="Special:BookSources/1-58488-237-9"><bdi>1-58488-237-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability+theory&rft.place=Boca+Raton%2C+FL&rft.pages=424&rft.pub=Chapman+%26+Hall%2FCRC&rft.date=2004&rft.isbn=1-58488-237-9&rft.aulast=Cooper&rft.aufirst=S.B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCutland1980" class="citation book cs1"><a href="/wiki/Nigel_Cutland" title="Nigel Cutland">Cutland, Nigel J.</a> (1980). <i>Computability, an introduction to recursive function theory</i>. Cambridge-New York: Cambridge University Press. p. 251. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-22384-9" title="Special:BookSources/0-521-22384-9"><bdi>0-521-22384-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability%2C+an+introduction+to+recursive+function+theory&rft.place=Cambridge-New+York&rft.pages=251&rft.pub=Cambridge+University+Press&rft.date=1980&rft.isbn=0-521-22384-9&rft.aulast=Cutland&rft.aufirst=Nigel+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span>; <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-29465-7" title="Special:BookSources/0-521-29465-7">0-521-29465-7</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Monographs_and_survey_articles_(graduate_level)"><span id="Monographs_and_survey_articles_.28graduate_level.29"></span>Monographs and survey articles (graduate level)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=13" title="Edit section: Monographs and survey articles (graduate level)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAmbos-SpiesFejer2006" class="citation web cs1">Ambos-Spies, Klaus; Fejer, Peter (20 March 2006). <a rel="nofollow" class="external text" href="http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf">"Degrees of Unsolvability"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">20 August</span> 2023</span>. <q>Unpublished</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Degrees+of+Unsolvability&rft.date=2006-03-20&rft.aulast=Ambos-Spies&rft.aufirst=Klaus&rft.au=Fejer%2C+Peter&rft_id=http%3A%2F%2Fwww.cs.umb.edu%2F~fejer%2Farticles%2FHistory_of_Degrees.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEpsteinHaasKramer1981" class="citation book cs1">Epstein, R.L.; Haas, R; Kramer, L.R. (1981). Leman, M; Schmerl, J.; Soare, R. (eds.). <i>Hierarchies of sets and degrees below 0</i>. Lecture Notes in Mathematics. Vol. 859. Springer-Verlag.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Hierarchies+of+sets+and+degrees+below+0&rft.series=Lecture+Notes+in+Mathematics&rft.pub=Springer-Verlag&rft.date=1981&rft.aulast=Epstein&rft.aufirst=R.L.&rft.au=Haas%2C+R&rft.au=Kramer%2C+L.R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLerman1983" class="citation book cs1">Lerman, M. (1983). <i>Degrees of unsolvability. Perspectives in Mathematical Logic</i>. Berlin: Springer-Verlag. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-12155-2" title="Special:BookSources/3-540-12155-2"><bdi>3-540-12155-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Degrees+of+unsolvability.+Perspectives+in+Mathematical+Logic&rft.place=Berlin&rft.pub=Springer-Verlag&rft.date=1983&rft.isbn=3-540-12155-2&rft.aulast=Lerman&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOdifreddi1989" class="citation book cs1"><a href="/wiki/Piergiorgio_Odifreddi" title="Piergiorgio Odifreddi">Odifreddi, Piergiorgio</a> (1989). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/classicalrecursi0000odif"><i>Classical Recursion Theory</i></a></span>. Studies in Logic and the Foundations of Mathematics. Vol. 125. Amsterdam: North-Holland. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-444-87295-1" title="Special:BookSources/978-0-444-87295-1"><bdi>978-0-444-87295-1</bdi></a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0982269">0982269</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Classical+Recursion+Theory&rft.place=Amsterdam&rft.series=Studies+in+Logic+and+the+Foundations+of+Mathematics&rft.pub=North-Holland&rft.date=1989&rft.isbn=978-0-444-87295-1&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D982269%23id-name%3DMR&rft.aulast=Odifreddi&rft.aufirst=Piergiorgio&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fclassicalrecursi0000odif&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOdifreddi1999" class="citation book cs1"><a href="/wiki/Piergiorgio_Odifreddi" title="Piergiorgio Odifreddi">Odifreddi, Piergiorgio</a> (1999). <i>Classical recursion theory. Vol. II</i>. Studies in Logic and the Foundations of Mathematics. Vol. 143. Amsterdam: North-Holland. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-444-50205-6" title="Special:BookSources/978-0-444-50205-6"><bdi>978-0-444-50205-6</bdi></a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1718169">1718169</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Classical+recursion+theory.+Vol.+II&rft.place=Amsterdam&rft.series=Studies+in+Logic+and+the+Foundations+of+Mathematics&rft.pub=North-Holland&rft.date=1999&rft.isbn=978-0-444-50205-6&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1718169%23id-name%3DMR&rft.aulast=Odifreddi&rft.aufirst=Piergiorgio&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRogers1967" class="citation book cs1"><a href="/wiki/Hartley_Rogers_Jr." title="Hartley Rogers Jr.">Rogers, Hartley</a> (1967). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/theoryofrecursiv00roge"><i>Theory of Recursive Functions and Effective Computability</i></a></span>. <a href="/wiki/Cambridge,_Massachusetts" title="Cambridge, Massachusetts">Cambridge, Massachusetts</a>: <a href="/wiki/MIT_Press" title="MIT Press">MIT Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780262680523" title="Special:BookSources/9780262680523"><bdi>9780262680523</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/933975989">933975989</a><span class="reference-accessdate">. Retrieved <span class="nowrap">6 May</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+Recursive+Functions+and+Effective+Computability&rft.place=Cambridge%2C+Massachusetts&rft.pub=MIT+Press&rft.date=1967&rft_id=info%3Aoclcnum%2F933975989&rft.isbn=9780262680523&rft.aulast=Rogers&rft.aufirst=Hartley&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ftheoryofrecursiv00roge&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSacks1966" class="citation book cs1"><a href="/wiki/Gerald_Sacks" title="Gerald Sacks">Sacks, G.E.</a> (1966). <i>Degrees of Unsolvability</i>. Annals of Mathematics Studies. Princeton University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-6910-7941-7" title="Special:BookSources/978-0-6910-7941-7"><bdi>978-0-6910-7941-7</bdi></a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/j.ctt1b9x0r8">j.ctt1b9x0r8</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Degrees+of+Unsolvability&rft.series=Annals+of+Mathematics+Studies&rft.pub=Princeton+University+Press&rft.date=1966&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2Fj.ctt1b9x0r8%23id-name%3DJSTOR&rft.isbn=978-0-6910-7941-7&rft.aulast=Sacks&rft.aufirst=G.E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSimpson1977a" class="citation journal cs1"><a href="/wiki/Steve_Simpson_(mathematician)" title="Steve Simpson (mathematician)">Simpson, Steven G.</a> (1977a). "Degrees of Unsolvability: A Survey of Results". <i>Annals of Mathematics Studies</i>. Studies in Logic and the Foundations of Mathematics. <b>90</b>. <a href="/wiki/Elsevier" title="Elsevier">Elsevier</a>: 631–652. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0049-237X%2808%2971117-0">10.1016/S0049-237X(08)71117-0</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780444863881" title="Special:BookSources/9780444863881"><bdi>9780444863881</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics+Studies&rft.atitle=Degrees+of+Unsolvability%3A+A+Survey+of+Results&rft.volume=90&rft.pages=631-652&rft.date=1977&rft_id=info%3Adoi%2F10.1016%2FS0049-237X%2808%2971117-0&rft.isbn=9780444863881&rft.aulast=Simpson&rft.aufirst=Steven+G.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShoenfield1971" class="citation book cs1"><a href="/wiki/Joseph_R._Shoenfield" title="Joseph R. Shoenfield">Shoenfield, Joseph R.</a> (1971). <i>Degrees of Unsolvability</i>. North-Holland/Elsevier. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7204-2061-6" title="Special:BookSources/978-0-7204-2061-6"><bdi>978-0-7204-2061-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Degrees+of+Unsolvability&rft.pub=North-Holland%2FElsevier&rft.date=1971&rft.isbn=978-0-7204-2061-6&rft.aulast=Shoenfield&rft.aufirst=Joseph+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShore1993" class="citation book cs1"><a href="/wiki/Richard_Shore" title="Richard Shore">Shore, R.</a> (1993). "The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond". In Univ. Nac. del Sur, Bahía Blanca (ed.). <i>Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992)</i>. Notas Lógica Mat. Vol. 38. pp. 61–70.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+theories+of+the+T%2C+tt%2C+and+wtt+r.e.+degrees%3A+undecidability+and+beyond&rft.btitle=Proceedings+of+the+IX+Latin+American+Symposium+on+Mathematical+Logic%2C+Part+1+%28Bah%C3%ADa+Blanca%2C+1992%29&rft.series=Notas+L%C3%B3gica+Mat.&rft.pages=61-70&rft.date=1993&rft.aulast=Shore&rft.aufirst=R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSoare1987" class="citation book cs1"><a href="/wiki/Robert_I._Soare" title="Robert I. Soare">Soare, Robert Irving</a> (1987). <i>Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets</i>. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-15299-7" title="Special:BookSources/3-540-15299-7"><bdi>3-540-15299-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Recursively+Enumerable+Sets+and+Degrees%3A+A+Study+of+Computable+Functions+and+Computably+Generated+Sets&rft.place=Berlin&rft.series=Perspectives+in+Mathematical+Logic&rft.pub=Springer-Verlag&rft.date=1987&rft.isbn=3-540-15299-7&rft.aulast=Soare&rft.aufirst=Robert+Irving&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSoare1978" class="citation journal cs1"><a href="/wiki/Robert_I._Soare" title="Robert I. Soare">Soare, Robert Irving</a> (1978). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1978-14552-2">"Recursively enumerable sets and degrees"</a>. <i>Bull. Amer. Math. Soc</i>. <b>84</b> (6): 1149–1181. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1978-14552-2">10.1090/S0002-9904-1978-14552-2</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0508451">0508451</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29549997">29549997</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bull.+Amer.+Math.+Soc.&rft.atitle=Recursively+enumerable+sets+and+degrees&rft.volume=84&rft.issue=6&rft.pages=1149-1181&rft.date=1978&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0508451%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A29549997%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1090%2FS0002-9904-1978-14552-2&rft.aulast=Soare&rft.aufirst=Robert+Irving&rft_id=https%3A%2F%2Fdoi.org%2F10.1090%252FS0002-9904-1978-14552-2&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading3"><h3 id="Research_papers">Research papers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=14" title="Edit section: Research papers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChongYu2007" class="citation journal cs1">Chong, C.T.; Yu, Liang (December 2007). <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/27588601">"Maximal Chains in the Turing Degrees"</a>. <i><a href="/wiki/Journal_of_Symbolic_Logic" title="Journal of Symbolic Logic">Journal of Symbolic Logic</a></i>. <b>72</b> (4): 1219–1227. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2178%2Fjsl%2F1203350783">10.2178/jsl/1203350783</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/27588601">27588601</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:38576214">38576214</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Symbolic+Logic&rft.atitle=Maximal+Chains+in+the+Turing+Degrees&rft.volume=72&rft.issue=4&rft.pages=1219-1227&rft.date=2007-12&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A38576214%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F27588601%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2178%2Fjsl%2F1203350783&rft.aulast=Chong&rft.aufirst=C.T.&rft.au=Yu%2C+Liang&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F27588601&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDeAntonio2010" class="citation web cs1">DeAntonio, Jasper (24 September 2010). <a rel="nofollow" class="external text" href="https://www.math.uchicago.edu/~may/VIGRE/VIGRE2010/REUPapers/DeAntonio.pdf">"The Turing degrees and their lack of linear order"</a> <span class="cs1-format">(PDF)</span><span class="reference-accessdate">. Retrieved <span class="nowrap">20 August</span> 2023</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+Turing+degrees+and+their+lack+of+linear+order&rft.date=2010-09-24&rft.aulast=DeAntonio&rft.aufirst=Jasper&rft_id=https%3A%2F%2Fwww.math.uchicago.edu%2F~may%2FVIGRE%2FVIGRE2010%2FREUPapers%2FDeAntonio.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKleenePost1954" class="citation cs2"><a href="/wiki/Stephen_Kleene" class="mw-redirect" title="Stephen Kleene">Kleene, Stephen Cole</a>; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>, Second Series, <b>59</b> (3): 379–407, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1969708">10.2307/1969708</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0003-486X">0003-486X</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1969708">1969708</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0061078">0061078</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=The+upper+semi-lattice+of+degrees+of+recursive+unsolvability&rft.volume=59&rft.issue=3&rft.pages=379-407&rft.date=1954&rft.issn=0003-486X&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0061078%23id-name%3DMR&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F1969708%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F1969708&rft.aulast=Kleene&rft.aufirst=Stephen+Cole&rft.au=Post%2C+Emil+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLachlan1966a" class="citation cs2">Lachlan, Alistair H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", <i>Proceedings of the London Mathematical Society</i>, <b>3</b> (1): 537–569, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7893">10.1.1.106.7893</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fs3-16.1.537">10.1112/plms/s3-16.1.537</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+London+Mathematical+Society&rft.atitle=Lower+Bounds+for+Pairs+of+Recursively+Enumerable+Degrees&rft.volume=3&rft.issue=1&rft.pages=537-569&rft.date=1966&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.106.7893%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1112%2Fplms%2Fs3-16.1.537&rft.aulast=Lachlan&rft.aufirst=Alistair+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLachlan1966b" class="citation cs2">Lachlan, Alistair H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", <i>J. Symb. Log.</i>, <b>31</b> (3): 434–454, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2270459">10.2307/2270459</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2270459">2270459</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:30992462">30992462</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+Symb.+Log.&rft.atitle=The+impossibility+of+finding+relative+complements+for+recursively+enumerable+degrees&rft.volume=31&rft.issue=3&rft.pages=434-454&rft.date=1966&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A30992462%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2270459%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F2270459&rft.aulast=Lachlan&rft.aufirst=Alistair+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLachlanSoare1980" class="citation cs2">Lachlan, Alistair H.; <a href="/wiki/Robert_I._Soare" title="Robert I. Soare">Soare, Robert Irving</a> (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", <i><a href="/wiki/Advances_in_Mathematics" title="Advances in Mathematics">Advances in Mathematics</a></i>, <b>37</b>: 78–82, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0001-8708%2880%2990027-4">10.1016/0001-8708(80)90027-4</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Advances+in+Mathematics&rft.atitle=Not+every+finite+lattice+is+embeddable+in+the+recursively+enumerable+degrees&rft.volume=37&rft.pages=78-82&rft.date=1980&rft_id=info%3Adoi%2F10.1016%2F0001-8708%2880%2990027-4&rft.aulast=Lachlan&rft.aufirst=Alistair+H.&rft.au=Soare%2C+Robert+Irving&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNiesShoreSlaman1998" class="citation cs2">Nies, André; Shore, Richard A.; <a href="/wiki/Theodore_Slaman" title="Theodore Slaman">Slaman, Theodore A.</a> (1998), "Interpretability and definability in the recursively enumerable degrees", <i>Proceedings of the London Mathematical Society</i>, <b>77</b> (2): 241–291, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.9588">10.1.1.29.9588</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2FS002461159800046X">10.1112/S002461159800046X</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0024-6115">0024-6115</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1635141">1635141</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16488410">16488410</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+London+Mathematical+Society&rft.atitle=Interpretability+and+definability+in+the+recursively+enumerable+degrees&rft.volume=77&rft.issue=2&rft.pages=241-291&rft.date=1998&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A16488410%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1112%2FS002461159800046X&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.29.9588%23id-name%3DCiteSeerX&rft.issn=0024-6115&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1635141%23id-name%3DMR&rft.aulast=Nies&rft.aufirst=Andr%C3%A9&rft.au=Shore%2C+Richard+A.&rft.au=Slaman%2C+Theodore+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPost1944" class="citation cs2">Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", <i><a href="/wiki/Bulletin_of_the_American_Mathematical_Society" title="Bulletin of the American Mathematical Society">Bulletin of the American Mathematical Society</a></i>, <b>50</b> (5): 284–316, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1944-08111-1">10.1090/S0002-9904-1944-08111-1</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0002-9904">0002-9904</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0010514">0010514</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bulletin+of+the+American+Mathematical+Society&rft.atitle=Recursively+enumerable+sets+of+positive+integers+and+their+decision+problems&rft.volume=50&rft.issue=5&rft.pages=284-316&rft.date=1944&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0010514%23id-name%3DMR&rft.issn=0002-9904&rft_id=info%3Adoi%2F10.1090%2FS0002-9904-1944-08111-1&rft.aulast=Post&rft.aufirst=Emil+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSacks1964" class="citation cs2"><a href="/wiki/Gerald_Sacks" title="Gerald Sacks">Sacks, G.E.</a> (1964), "The recursively enumerable degrees are dense", <i>Annals of Mathematics</i>, Second Series, <b>80</b> (2): 300–312, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1970393">10.2307/1970393</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1970393">1970393</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=The+recursively+enumerable+degrees+are+dense&rft.volume=80&rft.issue=2&rft.pages=300-312&rft.date=1964&rft_id=info%3Adoi%2F10.2307%2F1970393&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F1970393%23id-name%3DJSTOR&rft.aulast=Sacks&rft.aufirst=G.E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShoreSlaman1999" class="citation cs2"><a href="/wiki/Richard_Shore" title="Richard Shore">Shore, Richard A.</a>; <a href="/wiki/Theodore_Slaman" title="Theodore Slaman">Slaman, Theodore A.</a> (1999), "Defining the Turing jump", <i>Mathematical Research Letters</i>, <b>6</b> (6): 711–722, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4310%2Fmrl.1999.v6.n6.a10">10.4310/mrl.1999.v6.n6.a10</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1073-2780">1073-2780</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1739227">1739227</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematical+Research+Letters&rft.atitle=Defining+the+Turing+jump&rft.volume=6&rft.issue=6&rft.pages=711-722&rft.date=1999&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1739227%23id-name%3DMR&rft.issn=1073-2780&rft_id=info%3Adoi%2F10.4310%2Fmrl.1999.v6.n6.a10&rft.aulast=Shore&rft.aufirst=Richard+A.&rft.au=Slaman%2C+Theodore+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSimpson1977b" class="citation journal cs1"><a href="/wiki/Steve_Simpson_(mathematician)" title="Steve Simpson (mathematician)">Simpson, Stephen G.</a> (1977b). "First-order theory of the degrees of recursive unsolvability". <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>. Second Series. <b>105</b> (1): 121–139. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1971028">10.2307/1971028</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0003-486X">0003-486X</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1971028">1971028</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0432435">0432435</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=First-order+theory+of+the+degrees+of+recursive+unsolvability&rft.volume=105&rft.issue=1&rft.pages=121-139&rft.date=1977&rft.issn=0003-486X&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D0432435%23id-name%3DMR&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F1971028%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F1971028&rft.aulast=Simpson&rft.aufirst=Stephen+G.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFThomason1971" class="citation cs2">Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", <i>Z. Math. Logik Grundlag. Math.</i>, <b>17</b>: 273–280, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fmalq.19710170131">10.1002/malq.19710170131</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Z.+Math.+Logik+Grundlag.+Math.&rft.atitle=Sublattices+of+the+recursively+enumerable+degrees&rft.volume=17&rft.pages=273-280&rft.date=1971&rft_id=info%3Adoi%2F10.1002%2Fmalq.19710170131&rft.aulast=Thomason&rft.aufirst=S.K.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFYates1966" class="citation cs2">Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", <i>Journal of Symbolic Logic</i>, <b>31</b> (2): 159–168, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2269807">10.2307/2269807</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2269807">2269807</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:38778059">38778059</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Symbolic+Logic&rft.atitle=A+minimal+pair+of+recursively+enumerable+degrees&rft.volume=31&rft.issue=2&rft.pages=159-168&rft.date=1966&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A38778059%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2269807%23id-name%3DJSTOR&rft_id=info%3Adoi%2F10.2307%2F2269807&rft.aulast=Yates&rft.aufirst=C.E.M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATuring+degree" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Turing_degree&action=edit&section=15" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-FOOTNOTEDeAntonio20109-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEDeAntonio20109_1-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFDeAntonio2010">DeAntonio 2010</a>, p. 9.</span> </li> <li id="cite_note-FOOTNOTEChongYu20071224-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEChongYu20071224_2-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFChongYu2007">Chong & Yu 2007</a>, p. 1224.</span> </li> <li id="cite_note-FOOTNOTEOdifreddi1989252,_258-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEOdifreddi1989252,_258_3-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFOdifreddi1989">Odifreddi 1989</a>, p. 252, 258.</span> </li> <li id="cite_note-FOOTNOTEEpsteinHaasKramer1981-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-FOOTNOTEEpsteinHaasKramer1981_4-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><a href="#CITEREFEpsteinHaasKramer1981">Epstein, Haas & Kramer 1981</a>.</span> </li> </ol></div></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q1527413#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q1527413#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata" style="font-size:114%;margin:0 4em"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a> <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q1527413#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">International</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="http://id.worldcat.org/fast/1162046/">FAST</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh85141199">United States</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007529781805171">Israel</a></span></li></ul></div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Alan_Turing" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Alan_Turing" title="Template:Alan Turing"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Alan_Turing" title="Template talk:Alan Turing"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Alan_Turing" title="Special:EditPage/Template:Alan Turing"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Alan_Turing" style="font-size:114%;margin:0 4em"><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Turing_completeness" title="Turing completeness">Turing completeness</a></li> <li><a class="mw-selflink selflink">Turing degree</a></li> <li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Turing_pattern" title="Turing pattern">Turing pattern</a></li> <li><a href="/wiki/Turing%27s_proof" title="Turing's proof">Turing's proof</a></li> <li><a href="/wiki/Turing_reduction" title="Turing reduction">Turing reduction</a></li> <li><a href="/wiki/Turing_test" title="Turing test">Turing test</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Publications</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li>"<a href="/wiki/On_Computable_Numbers,_with_an_Application_to_the_Entscheidungsproblem" class="mw-redirect" title="On Computable Numbers, with an Application to the Entscheidungsproblem">On Computable Numbers</a>" (1936)</li> <li>"<a href="/wiki/Systems_of_Logic_Based_on_Ordinals" title="Systems of Logic Based on Ordinals">Systems of Logic Based on Ordinals</a>" (1939)</li> <li>"<a href="/wiki/Unorganized_machine" title="Unorganized machine">Intelligent Machinery</a>" (1948)</li> <li>"<a href="/wiki/Computing_Machinery_and_Intelligence" title="Computing Machinery and Intelligence">Computing Machinery and Intelligence</a>" (1950)</li> <li>"<a href="/wiki/The_Chemical_Basis_of_Morphogenesis" title="The Chemical Basis of Morphogenesis">The Chemical Basis of Morphogenesis</a>" (1952)</li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Legacy_of_Alan_Turing" title="Legacy of Alan Turing">Legacy of Alan Turing</a> <ul><li><a href="/wiki/List_of_things_named_after_Alan_Turing" title="List of things named after Alan Turing">namesakes</a></li></ul></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Turing_degree&oldid=1247797080">https://en.wikipedia.org/w/index.php?title=Turing_degree&oldid=1247797080</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Computability_theory" title="Category:Computability theory">Computability theory</a></li><li><a href="/wiki/Category:Theory_of_computation" title="Category:Theory of computation">Theory of computation</a></li><li><a href="/wiki/Category:Alan_Turing" title="Category:Alan Turing">Alan Turing</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</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"> This page was last edited on 26 September 2024, at 01:59<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Turing_degree&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</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-76c6b8f495-s65hs","wgBackendResponseTime":199,"wgPageParseReport":{"limitreport":{"cputime":"0.527","walltime":"0.848","ppvisitednodes":{"value":2575,"limit":1000000},"postexpandincludesize":{"value":69283,"limit":2097152},"templateargumentsize":{"value":1113,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":79586,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 678.044 1 -total"," 19.74% 133.824 1 Template:Short_description"," 19.37% 131.356 11 Template:Cite_book"," 18.46% 125.183 1 Template:Authority_control"," 10.44% 70.812 10 Template:Citation"," 10.39% 70.452 10 Template:Main_other"," 9.89% 67.088 1 Template:SDcat"," 7.86% 53.297 2 Template:Pagetype"," 6.97% 47.282 13 Template:Harvtxt"," 5.08% 34.444 1 Template:Redirect"]},"scribunto":{"limitreport-timeusage":{"value":"0.358","limit":"10.000"},"limitreport-memusage":{"value":6828959,"limit":52428800},"limitreport-logs":"anchor_id_list = table#1 {\n [\"CITEREFAmbos-SpiesFejer2006\"] = 1,\n [\"CITEREFChongYu2007\"] = 1,\n [\"CITEREFCooper2004\"] = 1,\n [\"CITEREFCutland1980\"] = 1,\n [\"CITEREFDeAntonio2010\"] = 1,\n [\"CITEREFEpsteinHaasKramer1981\"] = 1,\n [\"CITEREFKleenePost1954\"] = 1,\n [\"CITEREFLachlan1966a\"] = 1,\n [\"CITEREFLachlan1966b\"] = 1,\n [\"CITEREFLachlanSoare1980\"] = 1,\n [\"CITEREFLerman1983\"] = 1,\n [\"CITEREFNiesShoreSlaman1998\"] = 1,\n [\"CITEREFOdifreddi1989\"] = 1,\n [\"CITEREFOdifreddi1999\"] = 1,\n [\"CITEREFPost1944\"] = 1,\n [\"CITEREFRogers1967\"] = 1,\n [\"CITEREFSacks1964\"] = 1,\n [\"CITEREFSacks1966\"] = 1,\n [\"CITEREFShoenfield1971\"] = 1,\n [\"CITEREFShore1993\"] = 1,\n [\"CITEREFShoreSlaman1999\"] = 1,\n [\"CITEREFSimpson1977a\"] = 1,\n [\"CITEREFSimpson1977b\"] = 1,\n [\"CITEREFSoare1978\"] = 1,\n [\"CITEREFSoare1987\"] = 1,\n [\"CITEREFThomason1971\"] = 1,\n [\"CITEREFYates1966\"] = 1,\n}\ntemplate_list = table#1 {\n [\"Alan Turing\"] = 1,\n [\"Authority control\"] = 1,\n [\"Citation\"] = 10,\n [\"Cite book\"] = 11,\n [\"Cite journal\"] = 4,\n [\"Cite web\"] = 2,\n [\"Harvtxt\"] = 13,\n [\"Isbn\"] = 1,\n [\"Main\"] = 1,\n [\"Nowrap\"] = 5,\n [\"Redirect\"] = 1,\n [\"Reflist\"] = 1,\n [\"Sfn\"] = 6,\n [\"Short description\"] = 1,\n}\narticle_whitelist = table#1 {\n}\n"},"cachereport":{"origin":"mw-web.eqiad.main-559c9fd9f4-rzxqd","timestamp":"20241126125333","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Turing degree","url":"https:\/\/en.wikipedia.org\/wiki\/Turing_degree","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1527413","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1527413","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-06-29T18:44:10Z","dateModified":"2024-09-26T01:59:07Z","headline":"measurement for the level of algorithmic unsolvability of a set"}</script> </body> </html>