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>Alternating Turing machine - 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":"64b6165e-5832-4d63-8eaa-7be3db5e0fa4","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Alternating_Turing_machine","wgTitle":"Alternating Turing machine","wgCurRevisionId":1209127404,"wgRevisionId":1209127404,"wgArticleId":753230,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Articles lacking in-text citations from May 2011","All articles lacking in-text citations","Articles needing additional references from October 2013","All articles needing additional references","All articles with unsourced statements","Articles with unsourced statements from August 2010","Models of computation"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel": "wikitext","wgRelevantPageName":"Alternating_Turing_machine","wgRelevantArticleId":753230,"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":10000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q438833","wgCheckUserClientHintsHeadersJsApi":["brands", "architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.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.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%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.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Alternating Turing machine - 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/Alternating_Turing_machine"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Alternating_Turing_machine&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/Alternating_Turing_machine"> <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-Alternating_Turing_machine rootpage-Alternating_Turing_machine 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=Alternating+Turing+machine" 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=Alternating+Turing+machine" 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=Alternating+Turing+machine" 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=Alternating+Turing+machine" 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-Definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definitions</span> </div> </a> <button aria-controls="toc-Definitions-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 Definitions subsection</span> </button> <ul id="toc-Definitions-sublist" class="vector-toc-list"> <li id="toc-Informal_description" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Informal_description"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Informal description</span> </div> </a> <ul id="toc-Informal_description-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formal_definition" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Formal_definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Formal definition</span> </div> </a> <ul id="toc-Formal_definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Resource_bounds" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Resource_bounds"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Resource bounds</span> </div> </a> <ul id="toc-Resource_bounds-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Example" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Example"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Example</span> </div> </a> <ul id="toc-Example-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complexity_classes_and_comparison_to_deterministic_Turing_machines" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complexity_classes_and_comparison_to_deterministic_Turing_machines"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Complexity classes and comparison to deterministic Turing machines</span> </div> </a> <ul id="toc-Complexity_classes_and_comparison_to_deterministic_Turing_machines-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bounded_alternation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bounded_alternation"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Bounded alternation</span> </div> </a> <button aria-controls="toc-Bounded_alternation-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 Bounded alternation subsection</span> </button> <ul id="toc-Bounded_alternation-sublist" class="vector-toc-list"> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Example_2" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Example_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Example</span> </div> </a> <ul id="toc-Example_2-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Collapsing_classes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Collapsing_classes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Collapsing classes</span> </div> </a> <ul id="toc-Collapsing_classes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Special_cases" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Special_cases"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Special cases</span> </div> </a> <ul id="toc-Special_cases-sublist" class="vector-toc-list"> </ul> </li> </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">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Further reading</span> </div> </a> <ul id="toc-Further_reading-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">Alternating Turing machine</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 10 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-10" 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">10 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/M%C3%A0quina_de_Turing_alternant" title="Màquina de Turing alternant – Catalan" lang="ca" hreflang="ca" data-title="Màquina de Turing alternant" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Alternierende_Turingmaschine" title="Alternierende Turingmaschine – German" lang="de" hreflang="de" data-title="Alternierende Turingmaschine" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing_alternante" title="Máquina de Turing alternante – Spanish" lang="es" hreflang="es" data-title="Máquina de Turing alternante" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF_%D9%85%D8%AA%D9%86%D8%A7%D9%88%D8%A8" title="ماشین تورینگ متناوب – Persian" lang="fa" hreflang="fa" data-title="ماشین تورینگ متناوب" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Machine_de_Turing_alternante" title="Machine de Turing alternante – French" lang="fr" hreflang="fr" data-title="Machine de Turing alternante" 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-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B5%90%EB%8C%80_%ED%8A%9C%EB%A7%81_%EA%B8%B0%EA%B3%84" title="교대 튜링 기계 – Korean" lang="ko" hreflang="ko" data-title="교대 튜링 기계" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Alterniraju%C4%87i_Turingov_stroj" title="Alternirajući Turingov stroj – Croatian" lang="hr" hreflang="hr" data-title="Alternirajući Turingov stroj" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%A4%E6%9B%BF%E6%80%A7%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%A9%9F%E6%A2%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/M%C3%A1quina_de_Turing_alternada" title="Máquina de Turing alternada – Portuguese" lang="pt" hreflang="pt" data-title="Máquina de Turing alternada" 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-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%A4%E6%9B%BF%E5%BC%8F%E5%9B%BE%E7%81%B5%E6%9C%BA" 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/Q438833#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/Alternating_Turing_machine" 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:Alternating_Turing_machine" 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/Alternating_Turing_machine"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Alternating_Turing_machine&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=Alternating_Turing_machine&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/Alternating_Turing_machine"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Alternating_Turing_machine&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=Alternating_Turing_machine&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/Alternating_Turing_machine" 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/Alternating_Turing_machine" 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=Alternating_Turing_machine&oldid=1209127404" 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=Alternating_Turing_machine&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=Alternating_Turing_machine&id=1209127404&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%2FAlternating_Turing_machine"><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%2FAlternating_Turing_machine"><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=Alternating_Turing_machine&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=Alternating_Turing_machine&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/Q438833" 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">Abstract computation model</div> <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:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><style data-mw-deduplicate="TemplateStyles:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title"><a href="/wiki/Turing_machine" title="Turing machine">Turing machines</a></th></tr><tr><th class="sidebar-heading" style="background:#ddddff;"> Machine</th></tr><tr><td class="sidebar-content plainlist"> <ul><li><a href="/wiki/Turing_machine_equivalents" title="Turing machine equivalents">Turing machine equivalents</a></li> <li><a href="/wiki/Turing_machine_examples" title="Turing machine examples">Turing machine examples</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="background:#ddddff;"> Variants</th></tr><tr><td class="sidebar-content plainlist"> <ul><li><a class="mw-selflink selflink">Alternating Turing machine</a></li> <li><a href="/wiki/Neural_Turing_machine" title="Neural Turing machine">Neural Turing machine</a></li> <li><a href="/wiki/Nondeterministic_Turing_machine" title="Nondeterministic Turing machine">Nondeterministic Turing machine</a></li> <li><a href="/wiki/Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li> <li><a href="/wiki/Post%E2%80%93Turing_machine" title="Post–Turing machine">Post–Turing machine</a></li> <li><a href="/wiki/Probabilistic_Turing_machine" title="Probabilistic Turing machine">Probabilistic Turing machine</a></li> <li><a href="/wiki/Multitape_Turing_machine" title="Multitape Turing machine">Multitape Turing machine</a></li> <li><a href="/wiki/Multi-track_Turing_machine" title="Multi-track Turing machine">Multi-track Turing machine</a></li> <li><a href="/wiki/Symmetric_Turing_machine" title="Symmetric Turing machine">Symmetric Turing machine</a></li> <li><a href="/wiki/Decider_(Turing_machine)" title="Decider (Turing machine)">Total Turing machine</a></li> <li><a href="/wiki/Unambiguous_Turing_machine" title="Unambiguous Turing machine">Unambiguous Turing machine</a></li> <li><a href="/wiki/Universal_Turing_machine" title="Universal Turing machine">Universal Turing machine</a></li> <li><a href="/wiki/Zeno_machine" title="Zeno machine">Zeno machine</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="background:#ddddff;"> Science</th></tr><tr><td class="sidebar-content plainlist"> <ul><li><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a></li> <li><a href="/wiki/Category:Turing_machine" title="Category:Turing machine">Category:Turing machine</a></li></ul></td> </tr><tr><td class="sidebar-navbar"><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:Turing" title="Template:Turing"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Turing" title="Template talk:Turing"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Turing" title="Special:EditPage/Template:Turing"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-More_footnotes_needed plainlinks metadata ambox ambox-style ambox-More_footnotes_needed" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/40px-Text_document_with_red_question_mark.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/60px-Text_document_with_red_question_mark.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/80px-Text_document_with_red_question_mark.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article includes a list of <a href="/wiki/Wikipedia:Citing_sources#General_references" title="Wikipedia:Citing sources">general references</a>, but <b>it lacks sufficient corresponding <a href="/wiki/Wikipedia:Citing_sources#Inline_citations" title="Wikipedia:Citing sources">inline citations</a></b>.<span class="hide-when-compact"> Please help to <a href="/wiki/Wikipedia:WikiProject_Reliability" title="Wikipedia:WikiProject Reliability">improve</a> this article by <a href="/wiki/Wikipedia:When_to_cite" title="Wikipedia:When to cite">introducing</a> more precise citations.</span> <span class="date-container"><i>(<span class="date">May 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>In <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, an <b>alternating Turing machine</b> (<b>ATM</b>) is a <a href="/wiki/Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machine</a> (<b>NTM</b>) with a rule for accepting computations that generalizes the rules used in the definition of the <a href="/wiki/Complexity_class" title="Complexity class">complexity classes</a> <a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a> and <a href="/wiki/Co-NP" title="Co-NP">co-NP</a>. The concept of an ATM was set forth by <a href="/wiki/Ashok_K._Chandra" title="Ashok K. Chandra">Chandra</a> and <a href="/wiki/Larry_Stockmeyer" title="Larry Stockmeyer">Stockmeyer</a><sup id="cite_ref-chasto_1-0" class="reference"><a href="#cite_note-chasto-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and independently by <a href="/wiki/Dexter_Kozen" title="Dexter Kozen">Kozen</a><sup id="cite_ref-kozen_2-0" class="reference"><a href="#cite_note-kozen-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> in 1976, with a joint journal publication in 1981.<sup id="cite_ref-alternation_3-0" class="reference"><a href="#cite_note-alternation-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=1" title="Edit section: Definitions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Informal_description">Informal description</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=2" title="Edit section: Informal description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The definition of NP uses the <i>existential mode</i> of computation: if <i>any</i> choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the <i>universal mode</i> of computation: only if <i>all</i> choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes. </p><p>An <b>alternating Turing machine</b> is a <a href="/wiki/Non-deterministic_Turing_machine" class="mw-redirect" title="Non-deterministic Turing machine">non-deterministic Turing machine</a> whose states are divided into two sets: <b>existential states</b> and <b>universal states</b>. An existential state is accepting if some transition leads to an accepting state; a universal state is accepting if every transition leads to an accepting state. (Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally). The machine as a whole accepts if the initial state is accepting. </p> <div class="mw-heading mw-heading3"><h3 id="Formal_definition">Formal definition</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=3" title="Edit section: Formal definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Formally, a (one-tape) <b>alternating Turing machine</b> is a 5-<a href="/wiki/Tuple" title="Tuple">tuple</a> <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 M=(Q,\Gamma ,\delta ,q_{0},g)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>Q</mi> <mo>,</mo> <mi mathvariant="normal">Γ</mi> <mo>,</mo> <mi>δ</mi> <mo>,</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mi>g</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/adf64292d9b1bd1a9be317f53d671d5542d2889f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.033ex; height:2.843ex;" alt="{\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}"></span> where </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}"></span> is the finite set of states</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.453ex; height:2.176ex;" alt="{\displaystyle \Gamma }"></span> is the finite tape alphabet</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>:</mo> <mi>Q</mi> <mo>×</mo> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>Q</mi> <mo>×</mo> <mi mathvariant="normal">Γ</mi> <mo>×</mo> <mo fence="false" stretchy="false">{</mo> <mi>L</mi> <mo>,</mo> <mi>R</mi> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f71066a4292e9d6d7e638a772d90d36a0ab6a62e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.922ex; height:2.843ex;" alt="{\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}"></span> is called the transition function (<i>L</i> shifts the head left and <i>R</i> shifts the head right)</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}\in Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>∈</mo> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{0}\in Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ad0e7ce55cfad982929c93e29139a65108c37263" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.77ex; height:2.509ex;" alt="{\displaystyle q_{0}\in Q}"></span> is the initial state</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 g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo>:</mo> <mi>Q</mi> <mo stretchy="false">→</mo> <mo fence="false" stretchy="false">{</mo> <mo>∧</mo> <mo>,</mo> <mo>∨</mo> <mo>,</mo> <mi>a</mi> <mi>c</mi> <mi>c</mi> <mi>e</mi> <mi>p</mi> <mi>t</mi> <mo>,</mo> <mi>r</mi> <mi>e</mi> <mi>j</mi> <mi>e</mi> <mi>c</mi> <mi>t</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e4a336d67e0607f41f39fc8c9919726298825d39" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.389ex; height:2.843ex;" alt="{\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}"></span> specifies the type of each state</li></ul> <p>If <i>M</i> is in a state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\in Q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> <mo>∈</mo> <mi>Q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q\in Q}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/960b889a6324eeccc02725962bf11ac1a96c32fd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.749ex; height:2.509ex;" alt="{\displaystyle q\in Q}"></span> 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 g(q)=accept}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>a</mi> <mi>c</mi> <mi>c</mi> <mi>e</mi> <mi>p</mi> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(q)=accept}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/141fa031bcf7b934cac00b035365709d97b8b02e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.429ex; height:2.843ex;" alt="{\displaystyle g(q)=accept}"></span> then that configuration is said to be <i>accepting</i>, and if <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(q)=reject}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>r</mi> <mi>e</mi> <mi>j</mi> <mi>e</mi> <mi>c</mi> <mi>t</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(q)=reject}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/acbf35328af20387922d4d1441c7c9c05ba377a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.113ex; height:2.843ex;" alt="{\displaystyle g(q)=reject}"></span> the configuration is said to be <i>rejecting</i>. A configuration 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 g(q)=\wedge }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>∧</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(q)=\wedge }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e3ff915ecdf9d174937e66b452db9c3ce4d342c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.644ex; height:2.843ex;" alt="{\displaystyle g(q)=\wedge }"></span> is said to be accepting if all configurations reachable in one step are accepting, and rejecting if some configuration reachable in one step is rejecting. A configuration 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 g(q)=\vee }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>q</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo>∨</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(q)=\vee }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f71835eb2c46926b05f9cfcb6c8181bef6293c8e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.644ex; height:2.843ex;" alt="{\displaystyle g(q)=\vee }"></span> is said to be accepting when there exists some configuration reachable in one step that is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in a classical NTM except the final state). <i>M</i> is said to accept an input string <i>w</i> if the initial configuration of <i>M</i> (the state of <i>M</i> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d68d37de188ac61f0c0e3f31d5322d1c486f2f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{0}}"></span>, the head is at the left end of the tape, and the tape contains <i>w</i>) is accepting, and to reject if the initial configuration is rejecting. </p><p>Note that it is impossible for a configuration to be both accepting and rejecting, however, some configurations may be neither accepting or rejecting, due to the possibility of nonterminating computations. </p> <div class="mw-heading mw-heading3"><h3 id="Resource_bounds">Resource bounds</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=4" title="Edit section: Resource bounds"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not always necessary to examine all configurations reachable from the current configuration. In particular, an existential configuration can be labelled as accepting if any successor configuration is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting. </p><p>An ATM decides a <a href="/wiki/Formal_language" title="Formal language">formal language</a> in time <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 t(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70b64a27c4f55221162f329285382cc470e3827e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}"></span> if, on any input of length <span class="texhtml mvar" style="font-style:italic;">n</span>, examining configurations only up to <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 t(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/70b64a27c4f55221162f329285382cc470e3827e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}"></span> steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space <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(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d659eab6d8874e2cb6124fd2fc66b477b128c006" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.294ex; height:2.843ex;" alt="{\displaystyle s(n)}"></span> if examining configurations that do not modify tape cells beyond the <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(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d659eab6d8874e2cb6124fd2fc66b477b128c006" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.294ex; height:2.843ex;" alt="{\displaystyle s(n)}"></span> cell from the left is sufficient. </p><p>A language that is decided by some ATM in time <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 c\cdot t(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mo>⋅</mo> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c\cdot t(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cb1acd06cf40eb13e4425d8684c0010765906764" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.73ex; height:2.843ex;" alt="{\displaystyle c\cdot t(n)}"></span> for some constant <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 c>0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mo>></mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c>0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>0}"></span> is said to be in the class <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 {\mathsf {ATIME}}(t(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ATIME}}(t(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/da8641ac41da907ff6da39f9b46a674094fa00d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.054ex; height:2.843ex;" alt="{\displaystyle {\mathsf {ATIME}}(t(n))}"></span>, and a language decided in space <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 c\cdot s(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mo>⋅</mo> <mi>s</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle c\cdot s(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7045cae4656cd67c5329d8f484053af374bfe7bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.98ex; height:2.843ex;" alt="{\displaystyle c\cdot s(n)}"></span> is said to be in the class <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 {\mathsf {ASPACE}}(s(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>s</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ASPACE}}(s(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/426f4c14778a6e299918f1aa21cd9875f5a0547d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.855ex; height:2.843ex;" alt="{\displaystyle {\mathsf {ASPACE}}(s(n))}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Example">Example</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=5" title="Edit section: Example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Perhaps the most natural problem for alternating machines to solve is the <a href="/wiki/Quantified_Boolean_formula_problem" class="mw-redirect" title="Quantified Boolean formula problem">quantified Boolean formula problem</a>, which is a generalization of the <a href="/wiki/Boolean_satisfiability_problem" title="Boolean satisfiability problem">Boolean satisfiability problem</a> in which each variable can be bound by either an existential or a universal quantifier. The alternating machine branches existentially to try all possible values of an existentially quantified variable and universally to try all possible values of a universally quantified variable, in the left-to-right order in which they are bound. After deciding a value for all quantified variables, the machine accepts if the resulting Boolean formula evaluates to true, and rejects if it evaluates to false. Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable that renders the remaining problem satisfiable, and at a universally quantified variable the machine is accepting if any value can be substituted and the remaining problem is satisfiable. </p><p>Such a machine decides quantified Boolean formulas in time <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 n^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac9810bbdafe4a6a8061338db0f74e25b7952620" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}"></span> and space <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 n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. </p><p>The Boolean satisfiability problem can be viewed as the special case where all variables are existentially quantified, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently. </p> <div class="mw-heading mw-heading2"><h2 id="Complexity_classes_and_comparison_to_deterministic_Turing_machines">Complexity classes and comparison to deterministic Turing machines</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=6" title="Edit section: Complexity classes and comparison to deterministic Turing machines"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following <a href="/wiki/Complexity_classes" class="mw-redirect" title="Complexity classes">complexity classes</a> are useful to define for ATMs: </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>></mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee97080ce66b20a372ef32b2b12e3bef5d798b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:20.972ex; height:5.676ex;" alt="{\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}"></span> are the languages decidable in polynomial time</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 {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>></mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/02166a29a3b3f8171da034d809922a138c3f4aa5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:29.724ex; height:5.676ex;" alt="{\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}"></span> are the languages decidable in polynomial space</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 {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>></mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b167103f666ca0ce9e39874d17b83a65406e7dfd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:30.318ex; height:5.843ex;" alt="{\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}"></span> are the languages decidable in exponential time</li></ul> <p>These are similar to the definitions of <a href="/wiki/P_(complexity)" title="P (complexity)">P</a>, <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a>, and <a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a>, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer<sup id="cite_ref-alternation_3-1" class="reference"><a href="#cite_note-alternation-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> proved the theorems </p> <ul><li>ALOGSPACE = P</li> <li>AP = PSPACE</li> <li>APSPACE = EXPTIME</li> <li>AEXPTIME = <a href="/wiki/EXPSPACE" title="EXPSPACE">EXPSPACE</a></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 {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>c</mi> <mo>></mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">D</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>c</mi> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">D</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b268621775d65c0d9fa52dc52f8539c1f494ad45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:55.09ex; height:5.509ex;" alt="{\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}"></span></li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">D</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59aa03efa0a915cfef871e45e4df04e01861b2a9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.438ex; height:2.843ex;" alt="{\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}"></span></li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">N</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo>⊆</mo> <munder> <mo>⋃</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>c</mi> <mo>></mo> <mn>0</mn> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>c</mi> <mo>×</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1acc3bd696a65aa62ad6a400a73264c4cef7f4f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:40.153ex; height:5.509ex;" alt="{\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}"></span></li></ul> <p>when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)\geq \log(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(n)\geq \log(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6ae73cc99c5cbb8ac9e0bc5e292a6df5c3f98d82" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.757ex; height:2.843ex;" alt="{\displaystyle f(n)\geq \log(n)}"></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 g(n)\geq \log(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(n)\geq \log(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7155b9072e0b06f46d6cf2027e8be2f98a2a13b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.594ex; height:2.843ex;" alt="{\displaystyle g(n)\geq \log(n)}"></span>. </p><p>A more general form of these relationships is expressed by the <a href="/wiki/Parallel_computation_thesis" title="Parallel computation thesis">parallel computation thesis</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Bounded_alternation">Bounded alternation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=7" title="Edit section: Bounded alternation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Definition">Definition</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=8" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Unreferenced_section plainlinks metadata ambox ambox-content ambox-Unreferenced" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Question_book-new.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/50px-Question_book-new.svg.png" decoding="async" width="50" height="39" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/75px-Question_book-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/99/Question_book-new.svg/100px-Question_book-new.svg.png 2x" data-file-width="512" data-file-height="399" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>does not <a href="/wiki/Wikipedia:Citing_sources" title="Wikipedia:Citing sources">cite</a> any <a href="/wiki/Wikipedia:Verifiability" title="Wikipedia:Verifiability">sources</a></b>.<span class="hide-when-compact"> Please help <a href="/wiki/Special:EditPage/Alternating_Turing_machine" title="Special:EditPage/Alternating Turing machine">improve this section</a> by <a href="/wiki/Help:Referencing_for_beginners" title="Help:Referencing for beginners">adding citations to reliable sources</a>. Unsourced material may be challenged and <a href="/wiki/Wikipedia:Verifiability#Burden_of_evidence" title="Wikipedia:Verifiability">removed</a>.</span> <span class="date-container"><i>(<span class="date">October 2013</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p>An <b>alternating Turing machine with <i>k</i> alternations</b> is an alternating Turing machine that switches from an existential to a universal state or vice versa no more than <i>k</i>−1 times. (It is an alternating Turing machine whose states are divided into <i>k</i> sets. The states in even-numbered sets are universal and the states in odd-numbered sets are existential (or vice versa). The machine has no transitions between a state in set <i>i</i> and a state in set <i>j</i> < <i>i</i>.) </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo>,</mo> <mi>j</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d40b09802a488eda8dec25d406830831cb465fac" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:27.682ex; height:3.009ex;" alt="{\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}"></span> is the class of languages decidable in time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\in C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>∈</mo> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\in C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/816d11dc83c171102c8bef3c95e5398a9eb74d70" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.886ex; height:2.509ex;" alt="{\displaystyle f\in C}"></span> by a machine beginning in an existential state and alternating at most <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 j-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f14166afa81127e8e7a2e093dec9e3f9d1a95de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;" alt="{\displaystyle j-1}"></span> times. It is called the <span class="texhtml mvar" style="font-style:italic;">j</span>th level of the <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 {\mathsf {TIME}}(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {TIME}}(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7c2cfc566e06d638f179d4424fb5e649b9799fc9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.226ex; height:2.843ex;" alt="{\displaystyle {\mathsf {TIME}}(C)}"></span> hierarchy. </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">c</mi> <mi mathvariant="sans-serif">o</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo>,</mo> <mi>j</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi mathvariant="normal">Π</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2c5b652d3e0d664b570f9ddfa7d3d24d9b9cd32" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:29.941ex; height:3.009ex;" alt="{\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}"></span> is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in <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 {\mathsf {ATIME}}(f,j)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">T</mi> <mi mathvariant="sans-serif">I</mi> <mi mathvariant="sans-serif">M</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>f</mi> <mo>,</mo> <mi>j</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ATIME}}(f,j)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aef03b6ef8be15649732c2c6e7e053962c824ee3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.281ex; height:2.843ex;" alt="{\displaystyle {\mathsf {ATIME}}(f,j)}"></span>. </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo>,</mo> <mi>j</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/180186d2cf23fa0ff53aa01a7971cfc1577258ce" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:30.782ex; height:3.009ex;" alt="{\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}"></span> is defined similarly for space bounded computation. </p> <div class="mw-heading mw-heading3"><h3 id="Example_2">Example</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=9" title="Edit section: Example"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Consider the <a href="/wiki/Circuit_minimization_problem" class="mw-redirect" title="Circuit minimization problem">circuit minimization problem</a>: given a circuit <i>A</i> computing a <a href="/wiki/Boolean_function" title="Boolean function">Boolean function</a> <i>f</i> and a number <i>n</i>, determine if there is a circuit with at most <i>n</i> gates that computes the same function <i>f</i>. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuit <i>B</i> with at most <i>n</i> gates, then switching to a universal state, guessing an input, and checking that the output of <i>B</i> on that input matches the output of <i>A</i> on that input). </p> <div class="mw-heading mw-heading3"><h3 id="Collapsing_classes">Collapsing classes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=10" title="Edit section: Collapsing classes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>It is said that a hierarchy <i>collapses</i> to level <span class="texhtml mvar" style="font-style:italic;">j</span> if every language in level <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 k\geq j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≥</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\geq j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/301014b7e4a7651b95e0f49b385e34b89d7a5b92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.268ex; height:2.509ex;" alt="{\displaystyle k\geq j}"></span> of the hierarchy is in its level <span class="texhtml mvar" style="font-style:italic;">j</span>. </p><p>As a corollary of the <a href="/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" title="Immerman–Szelepcsényi theorem">Immerman–Szelepcsényi theorem</a>, the logarithmic space hierarchy collapses to its first level.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> As a corollary the <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 {\mathsf {SPACE}}(f)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>f</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {SPACE}}(f)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/322e937377d715e7b997c0eb58022a8e4a75790a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.289ex; height:2.843ex;" alt="{\displaystyle {\mathsf {SPACE}}(f)}"></span> hierarchy collapses to its first level when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f=\Omega (\log )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>=</mo> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f=\Omega (\log )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec8918cdf62040ba324c5c4c9e42d1afb16c1661" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.836ex; height:2.843ex;" alt="{\displaystyle f=\Omega (\log )}"></span> is <a href="/wiki/Space_constructible" class="mw-redirect" title="Space constructible">space constructible</a><sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (August 2010)">citation needed</span></a></i>]</sup>. </p> <div class="mw-heading mw-heading3"><h3 id="Special_cases">Special cases</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=11" title="Edit section: Special cases"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An alternating Turing machine in polynomial time with <i>k</i> alternations, starting in an existential (respectively, universal) state can decide all the problems in the class <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{k}^{p}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma _{k}^{p}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a5cb650932b98b7caafa4b083b346a213e873bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.767ex; height:3.176ex;" alt="{\displaystyle \Sigma _{k}^{p}}"></span> (respectively, <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 \Pi _{k}^{p}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi mathvariant="normal">Π</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Pi _{k}^{p}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e6cacfe766b9b758d8267341f4e50494446f3d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.832ex; height:3.176ex;" alt="{\displaystyle \Pi _{k}^{p}}"></span>).<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> These classes are sometimes 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 \Sigma _{k}{\rm {P}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi mathvariant="normal">Σ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma _{k}{\rm {P}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af9c54070333ae873d04dedf24315ea2f004b77d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.35ex; height:2.509ex;" alt="{\displaystyle \Sigma _{k}{\rm {P}}}"></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 \Pi _{k}{\rm {P}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi mathvariant="normal">Π</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Pi _{k}{\rm {P}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46ca9c20e3256c0eefcab78abbfaf054c0f6e9e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.415ex; height:2.509ex;" alt="{\displaystyle \Pi _{k}{\rm {P}}}"></span>, respectively. See the <a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">polynomial hierarchy</a> article for details. </p><p>Another special case of time hierarchies is the <a href="/wiki/LH_(complexity)" title="LH (complexity)">logarithmic hierarchy</a>. </p> <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=Alternating_Turing_machine&action=edit&section=12" title="Edit section: References"><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-chasto-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-chasto_1-0">^</a></b></span> <span class="reference-text"><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="CITEREFChandraStockmeyer1976" class="citation conference cs1">Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". <i>Proc. 17th IEEE Symp. on Foundations of Computer Science</i>. Houston, Texas. pp. 98–108. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1976.4">10.1109/SFCS.1976.4</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Alternation&rft.btitle=Proc.+17th+IEEE+Symp.+on+Foundations+of+Computer+Science&rft.place=Houston%2C+Texas&rft.pages=98-108&rft.date=1976&rft_id=info%3Adoi%2F10.1109%2FSFCS.1976.4&rft.aulast=Chandra&rft.aufirst=Ashok+K.&rft.au=Stockmeyer%2C+Larry+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></span> </li> <li id="cite_note-kozen-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-kozen_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKozen1976" class="citation conference cs1">Kozen, D. (1976). "On parallelism in Turing machines". <i>Proc. 17th IEEE Symp. on Foundations of Computer Science</i>. Houston, Texas. pp. 89–97. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1976.20">10.1109/SFCS.1976.20</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F7056">1813/7056</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=On+parallelism+in+Turing+machines&rft.btitle=Proc.+17th+IEEE+Symp.+on+Foundations+of+Computer+Science&rft.place=Houston%2C+Texas&rft.pages=89-97&rft.date=1976&rft_id=info%3Ahdl%2F1813%2F7056&rft_id=info%3Adoi%2F10.1109%2FSFCS.1976.20&rft.aulast=Kozen&rft.aufirst=D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></span> </li> <li id="cite_note-alternation-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-alternation_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-alternation_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChandraKozenStockmeyer1981" class="citation journal cs1">Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160412232110/http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf">"Alternation"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>. <b>28</b> (1): 114–133. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F322234.322243">10.1145/322234.322243</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:238863413">238863413</a>. Archived from <a rel="nofollow" class="external text" href="http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf">the original</a> <span class="cs1-format">(PDF)</span> on April 12, 2016.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Alternation&rft.volume=28&rft.issue=1&rft.pages=114-133&rft.date=1981&rft_id=info%3Adoi%2F10.1145%2F322234.322243&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A238863413%23id-name%3DS2CID&rft.aulast=Chandra&rft.aufirst=Ashok+K.&rft.au=Kozen%2C+Dexter+C.&rft.au=Stockmeyer%2C+Larry+J.&rft_id=http%3A%2F%2Fusers.cis.fiu.edu%2F~giri%2Fteach%2F5420%2Ff01%2Fpapers%2Fp114-chandra.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFImmerman1988" class="citation journal cs1">Immerman, Neil (1988). <a rel="nofollow" class="external text" href="http://www.cs.umass.edu/~immerman/pub/space.pdf">"Nondeterministic space is closed under complementation"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>. <b>17</b> (5): 935–938. <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.54.5941">10.1.1.54.5941</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.1137%2F0217058">10.1137/0217058</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Nondeterministic+space+is+closed+under+complementation&rft.volume=17&rft.issue=5&rft.pages=935-938&rft.date=1988&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.54.5941%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1137%2F0217058&rft.aulast=Immerman&rft.aufirst=Neil&rft_id=http%3A%2F%2Fwww.cs.umass.edu%2F~immerman%2Fpub%2Fspace.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKozen2006" class="citation book cs1"><a href="/wiki/Dexter_Kozen" title="Dexter Kozen">Kozen, Dexter</a> (2006). <span class="id-lock-limited" title="Free access subject to limited trial, subscription normally required"><a rel="nofollow" class="external text" href="https://archive.org/details/theorycomputatio00koze"><i>Theory of Computation</i></a></span>. <a href="/wiki/Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. p. <a rel="nofollow" class="external text" href="https://archive.org/details/theorycomputatio00koze/page/n67">58</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781846282973" title="Special:BookSources/9781846282973"><bdi>9781846282973</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+Computation&rft.pages=58&rft.pub=Springer-Verlag&rft.date=2006&rft.isbn=9781846282973&rft.aulast=Kozen&rft.aufirst=Dexter&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ftheorycomputatio00koze&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Alternating_Turing_machine&action=edit&section=13" title="Edit section: Further reading"><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="CITEREFMichael_Sipser2006" class="citation book cs1"><a href="/wiki/Michael_Sipser" title="Michael Sipser">Michael Sipser</a> (2006). <i>Introduction to the Theory of Computation</i> (2nd ed.). PWS Publishing. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-534-95097-2" title="Special:BookSources/978-0-534-95097-2"><bdi>978-0-534-95097-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=Introduction+to+the+Theory+of+Computation&rft.edition=2nd&rft.pub=PWS+Publishing&rft.date=2006&rft.isbn=978-0-534-95097-2&rft.au=Michael+Sipser&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span> Section 10.3: Alternation, pp. 380–386.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChristos_Papadimitriou1993" class="citation book cs1"><a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a> (1993). <i>Computational Complexity</i> (1st ed.). Addison Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-53082-7" title="Special:BookSources/978-0-201-53082-7"><bdi>978-0-201-53082-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=Computational+Complexity&rft.edition=1st&rft.pub=Addison+Wesley&rft.date=1993&rft.isbn=978-0-201-53082-7&rft.au=Christos+Papadimitriou&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span> Section 16.2: Alternation, pp. 399–401.</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBakhadyr_KhoussainovAnil_Nerode2012" class="citation book cs1">Bakhadyr Khoussainov; <a href="/wiki/Anil_Nerode" title="Anil Nerode">Anil Nerode</a> (2012). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=wR_oBwAAQBAJ"><i>Automata Theory and its Applications</i></a>. Springer Science & Business Media. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4612-0171-7" title="Special:BookSources/978-1-4612-0171-7"><bdi>978-1-4612-0171-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=Automata+Theory+and+its+Applications&rft.pub=Springer+Science+%26+Business+Media&rft.date=2012&rft.isbn=978-1-4612-0171-7&rft.au=Bakhadyr+Khoussainov&rft.au=Anil+Nerode&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DwR_oBwAAQBAJ&rfr_id=info%3Asid%2Fen.wikipedia.org%3AAlternating+Turing+machine" class="Z3988"></span></li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Alternating_Turing_machine&oldid=1209127404">https://en.wikipedia.org/w/index.php?title=Alternating_Turing_machine&oldid=1209127404</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">Category</a>: <ul><li><a href="/wiki/Category:Models_of_computation" title="Category:Models of computation">Models of computation</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_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Articles_lacking_in-text_citations_from_May_2011" title="Category:Articles lacking in-text citations from May 2011">Articles lacking in-text citations from May 2011</a></li><li><a href="/wiki/Category:All_articles_lacking_in-text_citations" title="Category:All articles lacking in-text citations">All articles lacking in-text citations</a></li><li><a href="/wiki/Category:Articles_needing_additional_references_from_October_2013" title="Category:Articles needing additional references from October 2013">Articles needing additional references from October 2013</a></li><li><a href="/wiki/Category:All_articles_needing_additional_references" title="Category:All articles needing additional references">All articles needing additional references</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_August_2010" title="Category:Articles with unsourced statements from August 2010">Articles with unsourced statements from August 2010</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 20 February 2024, at 12:43<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=Alternating_Turing_machine&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-f69cdc8f6-tfkkl","wgBackendResponseTime":159,"wgPageParseReport":{"limitreport":{"cputime":"0.352","walltime":"0.693","ppvisitednodes":{"value":1374,"limit":1000000},"postexpandincludesize":{"value":34819,"limit":2097152},"templateargumentsize":{"value":1240,"limit":2097152},"expansiondepth":{"value":13,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":41109,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 524.568 1 -total"," 27.91% 146.424 1 Template:Reflist"," 23.04% 120.847 1 Template:Short_description"," 21.53% 112.964 1 Template:Turing"," 20.46% 107.342 1 Template:Sidebar"," 18.17% 95.340 2 Template:Cite_conference"," 14.55% 76.303 1 Template:More_footnotes"," 12.72% 66.723 2 Template:Ambox"," 12.69% 66.576 2 Template:Pagetype"," 7.01% 36.789 5 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.216","limit":"10.000"},"limitreport-memusage":{"value":5472088,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-zs76z","timestamp":"20241122144216","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Alternating Turing machine","url":"https:\/\/en.wikipedia.org\/wiki\/Alternating_Turing_machine","sameAs":"http:\/\/www.wikidata.org\/entity\/Q438833","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q438833","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-25T17:29:48Z","dateModified":"2024-02-20T12:43:39Z","headline":"abstract computation model"}</script> </body> </html>