Alternating Turing machine (original) (raw)
En teoria de la computació, una Màquina de Turing alternant (ATM) és una màquina de Turing no determinista amb una regla per acceptar computacions que generalitzen les regles usades en la definició de les classes de complexitat NP i co-NP.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la computació, una Màquina de Turing alternant (ATM) és una màquina de Turing no determinista amb una regla per acceptar computacions que generalitzen les regles usades en la definició de les classes de complexitat NP i co-NP. (ca) In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt. Erste akzeptieren eine Eingabe, wenn es eine mögliche Berechnung gibt, die akzeptiert, während zweite nur dann akzeptieren, wenn alle möglichen Berechnung akzeptieren. (de) 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 and independently by Kozen in 1976, with a joint journal publication in 1981. (en) En la teoría de la complejidad computacional, una máquina de Turing alternante (ATM) es una (NTM) con una regla para la aceptación de cómputos que generaliza las reglas usadas en la definición de las clases de complejidad NP y co-NP. El concepto de una ATM fue establecido por Chandra y en 1976 (ver referencias). (es) En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr) 교대 튜링 기계(Alternating Turing machine, ATM)는 비결정론적 튜링 기계에 몇가지 조건이 추가된 기계이다. (ko) 交替性チューリング機械（こうたいせいチューリングきかい、英: Alternating Turing Machine, ATM）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。 (ja) Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP. O conceito de uma ATM foi criado por Chandra e Stockmeyer e independentemente por Kozen em 1976 (veja as referências). (pt) 交替式图灵机（英語：Alternating Turing Machine, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。 (zh) |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=wR_oBwAAQBAJ%7Cyear |
| dbo:wikiPageID | 753230 (xsd:integer) |
| dbo:wikiPageLength | 12424 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1072613732 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Dexter_Kozen dbr:EXPSPACE dbr:Co-NP dbr:LH_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Tuple dbr:Larry_Stockmeyer dbr:EXPTIME dbr:Non-deterministic_Turing_machine dbr:PSPACE dbr:Formal_language dbr:Ashok_K._Chandra dbc:Models_of_computation dbr:Boolean_function dbr:Boolean_satisfiability_problem dbr:Polynomial_hierarchy dbr:Complexity_classes dbr:Immerman–Szelepcsényi_theorem dbr:Parallel_computation_thesis dbr:Circuit_minimization_problem dbr:Quantified_Boolean_formula_problem dbr:Space_constructible |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Cite_book dbt:More_footnotes dbt:Mvar dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Null dbt:Turing |
| dct:subject | dbc:Models_of_computation |
| gold:hypernym | dbr:Machine |
| rdf:type | dbo:Software yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | En teoria de la computació, una Màquina de Turing alternant (ATM) és una màquina de Turing no determinista amb una regla per acceptar computacions que generalitzen les regles usades en la definició de les classes de complexitat NP i co-NP. (ca) In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt. Erste akzeptieren eine Eingabe, wenn es eine mögliche Berechnung gibt, die akzeptiert, während zweite nur dann akzeptieren, wenn alle möglichen Berechnung akzeptieren. (de) 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 and independently by Kozen in 1976, with a joint journal publication in 1981. (en) En la teoría de la complejidad computacional, una máquina de Turing alternante (ATM) es una (NTM) con una regla para la aceptación de cómputos que generaliza las reglas usadas en la definición de las clases de complejidad NP y co-NP. El concepto de una ATM fue establecido por Chandra y en 1976 (ver referencias). (es) En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr) 교대 튜링 기계(Alternating Turing machine, ATM)는 비결정론적 튜링 기계에 몇가지 조건이 추가된 기계이다. (ko) 交替性チューリング機械（こうたいせいチューリングきかい、英: Alternating Turing Machine, ATM）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。 (ja) Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP. O conceito de uma ATM foi criado por Chandra e Stockmeyer e independentemente por Kozen em 1976 (veja as referências). (pt) 交替式图灵机（英語：Alternating Turing Machine, ATM）是计算复杂度理论中定义的一种非确定型图灵机（NTM）。与一般非确定型图灵机不同，交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。 (zh) |
| rdfs:label | Màquina de Turing alternant (ca) Alternierende Turingmaschine (de) Alternating Turing machine (en) Máquina de Turing alternante (es) Machine de Turing alternante (fr) 교대 튜링 기계 (ko) 交替性チューリング機械 (ja) Máquina de Turing alternada (pt) 交替式图灵机 (zh) |
| owl:sameAs | freebase:Alternating Turing machine yago-res:Alternating Turing machine wikidata:Alternating Turing machine dbpedia-ca:Alternating Turing machine dbpedia-de:Alternating Turing machine dbpedia-es:Alternating Turing machine dbpedia-fa:Alternating Turing machine dbpedia-fr:Alternating Turing machine dbpedia-hr:Alternating Turing machine dbpedia-ja:Alternating Turing machine dbpedia-ko:Alternating Turing machine dbpedia-pt:Alternating Turing machine dbpedia-zh:Alternating Turing machine https://global.dbpedia.org/id/44DBs |
| prov:wasDerivedFrom | wikipedia-en:Alternating_Turing_machine?oldid=1072613732&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Alternating_Turing_machine |
| is dbo:knownFor of | dbr:Ashok_K._Chandra |
| is dbo:wikiPageDisambiguates of | dbr:ATM |
| is dbo:wikiPageRedirects of | dbr:Alternating_turing_machine dbr:Alternation_(complexity) dbr:Universal_state_(Turing) dbr:Alternating_computation dbr:Existential_state |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:List_of_computability_and_complexity_topics dbr:Atime dbr:Double_exponential_function dbr:Presburger_arithmetic dbr:NC_(complexity) dbr:LH_(complexity) dbr:Alternating_turing_machine dbr:Computational_complexity_theory dbr:PH_(complexity) dbr:P_(complexity) dbr:Larry_Stockmeyer dbr:Alternation_(complexity) dbr:EXPTIME dbr:PSPACE dbr:2-EXPTIME dbr:ATM dbr:Ashok_K._Chandra dbr:AC_(complexity) dbr:Polynomial_hierarchy dbr:Universal_Turing_machine dbr:Universal_state_(Turing) dbr:Exponential_hierarchy dbr:Immerman–Szelepcsényi_theorem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_things_named_after_Alan_Turing dbr:Multitape_Turing_machine dbr:Parallel_computation_thesis dbr:True_quantified_Boolean_formula dbr:Alternating_computation dbr:Existential_state |
| is foaf:primaryTopic of | wikipedia-en:Alternating_Turing_machine |