Decider (Turing machine) (original) (raw)
En teoria de complexitat, una màquina que sempre s'atura - també coneguda com a decider o màquina de Turing total - és una màquina de Turing que s'atura per qualsevol entrada. Com que sempre s'atura, la màquina és capaç de decidir si la cadena d'entrada pertany o no a un llenguatge formal. La classe de llenguatges formals que es poden decidir per una màquina d'aquest tipus és la dels llenguatges recursius. Tot i això, el problema de la parada, que és decidir si una màquina de Turing arbitrària s'atura per una entrada donada, és un problema indecidible.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de complexitat, una màquina que sempre s'atura - també coneguda com a decider o màquina de Turing total - és una màquina de Turing que s'atura per qualsevol entrada. Com que sempre s'atura, la màquina és capaç de decidir si la cadena d'entrada pertany o no a un llenguatge formal. La classe de llenguatges formals que es poden decidir per una màquina d'aquest tipus és la dels llenguatges recursius. Tot i això, el problema de la parada, que és decidir si una màquina de Turing arbitrària s'atura per una entrada donada, és un problema indecidible. (ca) In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function. Because it always halts, such a machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is the set of recursive languages. Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem. This is a variant of the halting problem, which asks for whether a Turing machine halts on a specific input. (en) Nella teoria della computabilità una macchina che termina sempre, chiamata anche un decider o macchina di Turing totale, è un particolare di tipo di macchina di Turing per cui, al contrario del modello generale, vi è garanzia che termini per ogni input. Poiché si ferma sempre, la macchina è in grado di decidere se una data stringa è membro di un linguaggio formale. La classe dei linguaggi che possono essere decisi da macchine di questo tipo è esattamente l'insieme dei linguaggi ricorsivi. Dato il problema della fermata, determinare se un'arbitraria macchina di Turing termini sempre è indecidibile,non c'è nessun algoritmo per determinarlo. (it) Na teoria da computação, uma máquina de Turing que sempre para, também chamada de máquina de Turing total, é uma máquina de Turing que para para qualquer entrada. Como ela sempre para, a máquina é sempre capaz de decidir se uma determinada cadeia pertence a uma determinada linguagem formal. A classe de linguagens que podem ser decidida por estas máquinas é exatamente o conjunto das linguagens recursivas. No entanto, devido ao problema da parada, determinar quando uma Máquina de Turing para para uma entrada arbitrária é um problema indecidível. (pt) 在可计算性理论中，总是停机的机器也叫做判定器（Sipser，1996年）或全图灵机（Kozen，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。 (zh) |
| dbo:wikiPageExternalLink | https://www.researchgate.net/profile/Albert_Meyer/publication/234810406_The_complexity_of_loop_programs/links/00b49517fb0c8b6a2a000000.pdf |
| dbo:wikiPageID | 1352564 (xsd:integer) |
| dbo:wikiPageLength | 8921 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099615127 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Dennis_Ritchie dbr:Peano_arithmetic dbr:Decision_problem dbr:Decision_tree dbr:Dexter_Kozen dbr:Infinite_loop dbr:Introduction_to_the_Theory_of_Computation dbr:Computability_theory dbr:Consistent dbr:Control_flow dbc:Turing_machine dbr:Total_recursive_function dbr:Arithmetical_hierarchy dbr:Total_functional_programming dbr:BASIC dbr:Total_function dbr:Well-order dbr:Lawrence_Landweber dbr:Toy_programming_language dbr:Albert_R._Meyer dbr:First-order_logic dbr:Partial_functions dbr:Formal_language dbr:Recursively_enumerable dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Term_rewriting dbr:Ackermann_function dbr:BlooP_and_FlooP dbr:Termination_analysis dbr:Recursive_language dbr:Michael_Sipser dbr:Kleene's_recursion_theorem dbr:Turing_machine dbr:Soundness dbr:Undecidable_problem dbr:Primitive_recursive_functions dbr:Goodstein_sequence |
| dbp:wikiPageUsesTemplate | dbt:Main_article dbt:Mvar dbt:See_also dbt:Short_description dbt:Tmath dbt:Val dbt:Clarify_span dbt:Math_theorem dbt:Formal_languages_and_grammars |
| dcterms:subject | dbc:Turing_machine |
| rdf:type | owl:Thing |
| rdfs:comment | En teoria de complexitat, una màquina que sempre s'atura - també coneguda com a decider o màquina de Turing total - és una màquina de Turing que s'atura per qualsevol entrada. Com que sempre s'atura, la màquina és capaç de decidir si la cadena d'entrada pertany o no a un llenguatge formal. La classe de llenguatges formals que es poden decidir per una màquina d'aquest tipus és la dels llenguatges recursius. Tot i això, el problema de la parada, que és decidir si una màquina de Turing arbitrària s'atura per una entrada donada, és un problema indecidible. (ca) In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function. Because it always halts, such a machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is the set of recursive languages. Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem. This is a variant of the halting problem, which asks for whether a Turing machine halts on a specific input. (en) Na teoria da computação, uma máquina de Turing que sempre para, também chamada de máquina de Turing total, é uma máquina de Turing que para para qualquer entrada. Como ela sempre para, a máquina é sempre capaz de decidir se uma determinada cadeia pertence a uma determinada linguagem formal. A classe de linguagens que podem ser decidida por estas máquinas é exatamente o conjunto das linguagens recursivas. No entanto, devido ao problema da parada, determinar quando uma Máquina de Turing para para uma entrada arbitrária é um problema indecidível. (pt) 在可计算性理论中，总是停机的机器也叫做判定器（Sipser，1996年）或全图灵机（Kozen，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。 (zh) Nella teoria della computabilità una macchina che termina sempre, chiamata anche un decider o macchina di Turing totale, è un particolare di tipo di macchina di Turing per cui, al contrario del modello generale, vi è garanzia che termini per ogni input. (it) |
| rdfs:label | Màquina que sempre s'atura (ca) Decider (Turing machine) (en) Macchina che termina sempre (it) Máquina de Turing que sempre para (pt) 判定器 (zh) |
| rdfs:seeAlso | dbr:Termination_analysis |
| owl:sameAs | wikidata:Decider (Turing machine) dbpedia-ca:Decider (Turing machine) dbpedia-fa:Decider (Turing machine) dbpedia-hr:Decider (Turing machine) dbpedia-it:Decider (Turing machine) dbpedia-pt:Decider (Turing machine) dbpedia-sr:Decider (Turing machine) dbpedia-zh:Decider (Turing machine) https://global.dbpedia.org/id/2NGeP |
| prov:wasDerivedFrom | wikipedia-en:Decider_(Turing_machine)?oldid=1099615127&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Decider_(Turing_machine) |
| is dbo:wikiPageDisambiguates of | dbr:Decider |
| is dbo:wikiPageRedirects of | dbr:Decider_Turing_machine dbr:Total_Turing_machine dbr:Machine_that_always_halts dbr:Machines_that_always_halt dbr:Decider_(computability_theory) |
| is dbo:wikiPageWikiLink of | dbr:Decider_Turing_machine dbr:Total_Turing_machine dbr:Machine_that_always_halts dbr:Decider dbr:Machines_that_always_halt dbr:Decider_(computability_theory) |
| is foaf:primaryTopic of | wikipedia-en:Decider_(Turing_machine) |