Meta tags:

Headings (most frequently used words):

turing, example, classes, definition, alternating, machine, contents, definitions, complexity, and, comparison, to, deterministic, machines, bounded, alternation, references, further, reading, informal, description, formal, resource, bounds, collapsing, special, cases,

Text of the page (most frequently used words):
the (89), displaystyle (45), #machine (41), #turing (35), and (34), mathsf (24), state (22), accepting (22), edit (17), alternating (16), with (16), configuration (16), all (14), are (14), that (14), time (12), existential (12), universal (12), rejecting (12), this (11), for (11), computation (10), space (10), from (9), alternation (9), definition (9), can (8), log (8), said (8), problem (8), states (8), quantified (8), languages (7), wikipedia (7), articles (7), complexity (7), hierarchy (7), classes (7), atime (7), atm (7), 978 (6), level (6), when (6), one (6), boolean (6), times (6), any (6), variable (6), some (6), configurations (6), may (5), page (5), references (5), citations (5), isbn (5), doi (5), kozen (5), 1976 (5), machines (5), special (5), polynomial (5), article (5), language (5), input (5), bigcup (5), deterministic (5), initial (5), tape (5), reachable (5), toggle (4), contents (4), search (4), description (4), science (4), theory (4), its (4), section (4), pdf (4), chandra (4), stockmeyer (4), class (4), these (4), sigma (4), circuit (4), most (4), example (4), bounded (4), aspace (4), decidable (4), more (4), sets (4), set (4), definitions (4), existentially (4), which (4), left (4), accepts (4), step (4), accept (4), gamma (4), hide (4), move (4), sidebar (4), view (3), text (3), additional (3), non (3), was (3), unsourced (3), springer (3), journal (3), respectively (3), collapses (3), geq (3), function (3), solve (3), then (3), transitions (3), learn (3), help (3), not (3), general (3), uses (3), only (3), decides (3), universally (3), value (3), sufficient (3), formal (3), head (3), reject (3), transition (3), leads (3), whole (3), tools (3), main (3), table (2), contact (2), about (2), privacy (2), policy (2), under (2), terms (2), using (2), statements (2), needing (2), october (2), 2013 (2), lacking (2), 2011 (2), short (2), matches (2), wikidata (2), category (2), retrieved (2), balcázar (2), josé (2), luis (2), díaz (2), josep (2), gabarró (2), joaquim (2), 642 (2), 75357 (2), computational (2), 2006 (2), further (2), reading (2), dexter (2), immerman (2), computing (2), nondeterministic (2), ashok (2), larry (2), 1981 (2), houston (2), texas (2), 1109 (2), sfcs (2), proc (2), 17th (2), ieee (2), symp (2), foundations (2), computer (2), case (2), logarithmic (2), alternations (2), starting (2), cases (2), corollary (2), first (2), every (2), collapsing (2), there (2), gates (2), same (2), guessing (2), output (2), defined (2), but (2), beginning (2), called (2), vice (2), versa (2), than (2), whose (2), divided (2), into (2), numbered (2), between (2), how (2), remove (2), message (2), please (2), sources (2), improve (2), does (2), cite (2), aexptime (2), apspace (2), exptime (2), pspace (2), particular (2), subseteq (2), dtime (2), used (2), comparison (2), satisfiability (2), where (2), variables (2), such (2), each (2), bound (2), try (2), possible (2), values (2), right (2), deciding (2), formula (2), evaluates (2), rejects (2), thus (2), substituted (2), remaining (2), satisfiable (2), decided (2), cdot (2), examining (2), current (2), labelled (2), successor (2), found (2), resource (2), bounds (2), computations (2), type (2), ntm (2), vee (2), wedge (2), rightarrow (2), shifts (2), delta (2), finite (2), unconditionally (2), precise (2), mode (2), informal (2), appearance (2), upload (2), file (2), changes (2), links (2), history (2), read (2), subsection (2), create (2), account (2), donate (2), menu (2), add, topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, available, apply, site, you, agree, registered, trademark, profit, organization, wikimedia, foundation, inc, use, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, september, 2026, utc, hidden, categories, august, 2010, models, https, org, index, php, title, alternating_turing_machine, oldid, 1374409610, bakhadyr, khoussainov, 2012, business, media, 4612, 0171, automata, applications, anil, nerode, 1990, eds, berlin, heidelberg, 2025, 1007, 2_4, structural, 399, 401, 1993, 1st, addison, wesley, 201, 53082, christos, papadimitriou, 380, 386, 2nd, pws, publishing, 534, 95097, introduction, michael, sipser, 84628, 297, verlag, neil, 1988, 938, 1137, 0217058, 935, siam, closed, complementation, 133, archived, april, 2016, original, 238863413, s2cid, 1145, 322234, 322243, 114, acm, parallelism, 1813, 7056, hdl, 108, another, hierarchies, decide, problems, sometimes, denoted, see, details, citation, needed, constructible, omega, szelepcsényi, theorem, consider, given, number, determine, computes, switching, checking, minimization, similarly, way, consists, complements, coatime, switches, even, odd, has, material, challenged, removed, adding, reliable, form, relationships, expressed, parallel, thesis, expspace, alogspace, nspace, dspace, similar, considering, resources, rather, proved, exponential, following, useful, define, atms, viewed, allowing, ordinary, nondeterminism, branching, efficiently, formulas, perhaps, natural, generalization, either, quantifier, branches, order, they, after, resulting, true, false, renders, constant, length, steps, label, modify, cells, beyond, cell, above, always, necessary, examine, note, impossible, both, however, neither, due, possibility, nonterminating, exists, classical, except, final, string, end, contains, specifies, mathcal, alphabet, formally, tuple, two, choice, choices, lead, acceptance, alternates, modes, rule, generalizes, rules, concept, forth, independently, joint, publication, alan, zeno, unambiguous, total, symmetric, multi, track, multitape, probabilistic, post, quantum, neural, variants, examples, equivalents, includes, list, introducing, lacks, corresponding, inline, abstract, model, free, encyclopedia, item, other, projects, printable, version, download, print, export, switch, legacy, parser, get, shortened, url, information, permanent, link, related, what, here, actions, english, talk, português, 한국어, 日本語, hrvatski, français, فارسی, español, deutsch, català, top, personal, pages, recent, community, portal, contribute, random, events, navigation, jump, content,

Text of the page (random words):
alternating turing machine wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 definitions toggle definitions subsection 1 1 informal description 1 2 formal definition 1 3 resource bounds 2 example 3 complexity classes and comparison to deterministic turing machines 4 bounded alternation toggle bounded alternation subsection 4 1 definition 4 2 example 4 3 collapsing classes 4 4 special cases 5 references 6 further reading toggle the table of contents alternating turing machine 10 languages català deutsch español فارسی français hrvatski 日本語 한국어 português 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia abstract computation model this article includes a list of general references but lacks sufficient corresponding inline citations please help improve this article by introducing more precise citations may 2011 learn how and when to remove this message turing machines machine turing machine equivalents turing machine examples variants alternating turing machine neural turing machine nondeterministic turing machine quantum turing machine post turing machine probabilistic turing machine multitape turing machine multi track turing machine symmetric turing machine total turing machine unambiguous turing machine universal turing machine zeno machine science alan turing category turing machine v t e in computational complexity theory an alternating turing machine atm is a non deterministic turing machine ntm with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes np and co np the concept of an atm was set forth by chandra and stockmeyer 1 and independently by kozen 2 in 1976 with a joint journal publication in 1981 3 definitions edit informal description edit the definition of np uses the existential mode of computation if any choice leads to an accepting state then the whole computation accepts the definition of co np uses the universal mode of computation only if all 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 an alternating turing machine is a non deterministic turing machine whose states are divided into two sets existential states and universal states 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 formal definition edit formally a one tape alternating turing machine is a 5 tuple m q γ δ q 0 g displaystyle m q gamma delta q_ 0 g where q displaystyle q is the finite set of states γ displaystyle gamma is the finite tape alphabet δ q γ p q γ l r displaystyle delta q times gamma rightarrow mathcal p q times gamma times l r is called the transition function l shifts the head left and r shifts the head right q 0 q displaystyle q_ 0 in q is the initial state g q a c c e p t r e j e c t displaystyle g q rightarrow wedge vee accept reject specifies the type of each state if m is in a state q q displaystyle q in q with g q a c c e p t displaystyle g q accept then that configuration is said to be accepting and if g q r e j e c t displaystyle g q reject the configuration is said to be rejecting a configuration with g q displaystyle g q wedge 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 g q displaystyle g q vee 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 m is said to accept an input string w if the initial configuration of m the state of m is q 0 displaystyle q_ 0 the head is at the left end of the tape and the tape contains w is accepting and to reject if the initial configuration is rejecting 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 resource bounds edit 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 an atm decides a formal language in time t n displaystyle t n if on any input of length n examining configurations only up to t n displaystyle t n steps is sufficient to label the initial configuration as accepting or rejecting an atm decides a language in space s n displaystyle s n if examining configurations that do not modify tape cells beyond the s n displaystyle s n cell from the left is sufficient a language that is decided by some atm in time c t n displaystyle c cdot t n for some constant c 0 displaystyle c 0 is said to be in the class a t i m e t n displaystyle mathsf atime t n and a language decided in space c s n displaystyle c cdot s n is said to be in the class a s p a c e s n displaystyle mathsf aspace s n example edit perhaps the most natural problem for alternating machines to solve is the quantified boolean formula problem which is a generalization of the boolean satisfiability problem 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 such a machine decides quantified boolean formulas in time n 2 displaystyle n 2 and space n displaystyle n 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 complexity classes and comparison to deterministic turing machines edit the following complexity classes are useful to define for atms a p k 0 a t i m e n k displaystyle mathsf ap bigcup _ k 0 mathsf atime n k are the languages decidable in polynomial time a p s p a c e k 0 a s p a c e n k displaystyle mathsf apspace bigcup _ k 0 mathsf aspace n k are the languages decidable in polynomial space a e x p t i m e k 0 a t i m e 2 n k displaystyle mathsf aexptime bigcup _ k 0 mathsf atime 2 n k are the languages decidable in exponential time these are similar to the definitions of p pspace and exptime considering the resources used by an atm rather than a deterministic turing machine chandra kozen and stockmeyer 3 proved that for all f n log n displaystyle f n geq log n and g n log n displaystyle g n geq log n a s p a c e f n c 0 d t i m e 2 c f n d t i m e 2 o f n displaystyle mathsf aspace f n bigcup _ c 0 mathsf dtime 2 cf n mathsf dtime 2 o f n a t i m e g n d s p a c e g n displaystyle mathsf atime g n subseteq mathsf dspace g n n s p a c e g n c 0 a t i m e c g n 2 displaystyle mathsf nspace g n subseteq bigcup _ c 0 mathsf atime c times g n 2 in particular alogspace p ap pspace apspace exptime aexptime expspace a more general form of these relationships is expressed by the parallel computation thesis bounded alternation edit definition edit this section does not cite any sources please help improve this section by adding citations to reliable sources unsourced material may be challenged and removed october 2013 learn how and when to remove this message an alternating turing machine with k alternations is an alternating turing machine that switches from an existential to a universal state or vice versa no more than k 1 times it is an alternating turing machine whose states are divided into k 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 and a state in set j i a t i m e c j σ j t i m e c displaystyle mathsf atime c j sigma _ j mathsf time c is the class of languages decidable in time f c displaystyle f in c by a machine beginning in an existential state and alternating at most j 1 displaystyle j 1 times it is called the j th level of the t i m e c displaystyle mathsf time c hierarchy c o a t i m e c j π j t i m e c displaystyle mathsf coatime c j pi _ j mathsf time c is defined in the same way but beginning in a universal state it consists of the complements of the languages in a t i m e f j displaystyle mathsf atime f j a s p a c e c j σ j s p a c e c displaystyle mathsf aspace c j sigma _ j mathsf space c is defined similarly for space bounded computation example edit consider the circuit minimization problem given a circuit a computing a boolean function f and a number n determine if there is a circuit with at most n gates that computes the same function f an alternating turing machine with one alternation starting in an existential state can solve this problem in polynomial time by guessing a circuit b with at most n gates then switching to a universal state guessing an input and checking that the output of b on that input matches the output of a on that input collapsing classes edit it is said that a hierarchy collapses to level j if every language in level k j displaystyle k geq j of the hierarchy is in its level j as a corollary of the immerman szelepcsényi theorem the logarithmic space hierarchy collapses to its first level 4 as a corollary the s p a c e f displaystyle mathsf space f hierarchy collapses to its first level when f ω log displaystyle f omega log is space constructible citation needed special cases edit an alternating turing machine in polynomial time with k alternations starting in an existential respectively universal state can decide all the problems in the class σ k p displaystyle sigma _ k p respectively π k p displaystyle pi _ k p 5 these classes are sometimes denoted σ k p displaystyle sigma _ k rm p and π k p displaystyle pi _ k rm p respectively see the polynomial hierarchy article for details another special case of time hierarchies is the logarithmic hierarchy references edit chandra ashok k stockmeyer larry j 1976 alternation proc 17th ieee symp on foundations of computer science houston texas pp 98 108 doi 10 1109 sfcs 1976 4 kozen d 1976 on parallelism in turing machines proc 17th ieee symp on foundations of computer science houston texas pp 89 97 doi 10 1109 sfcs 1976 20 hdl 1813 7056 1 2 chandra ashok k kozen dexter c stockmeyer larry j 1981 alternation pdf journal of the acm 28 1 114 133 doi 10 1145 322234 322243 s2cid 238863413 archived from the original pdf on april 12 2016 immerman neil 1988 nondeterministic space is closed under complementation pdf siam journal on computing 17 5 935 938 doi 10 1137 0217058 kozen dexter 2006 theory of computation springer verlag p 58 isbn 978 1 84628 297 3 further reading edit michael sipser 2006 introduction to the theory of computation 2nd ed pws publishing isbn 978 0 534 95097 2 section 10 3 alternation pp 380 386 christos papadimitriou 1993 computational complexity 1st ed addison wesley isbn 978 0 201 53082 7 section 16 2 alternation pp 399 401 balcázar josé luis díaz josep gabarró joaquim 1990 alternation in balcázar josé luis díaz josep gabarró joaquim eds structural complexity ii berlin heidelberg springer pp 63 96 doi 10 1007 978 3 642 75357 2_4 isbn 978 3 642 75357 2 retrieved 2025 05 19 bakhadyr khoussainov anil nerode 2012 automata theory and its applications springer science business media isbn 978 1 4612 0171 7 retrieved from https en wikipedia org w index php title alternating_turing_machine oldid 1374409610 category models of computation hidden categories 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 this page was last edited on 11 september 2026 at 22 26 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents alternating turing machine 10 languages add topic