| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8921 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| 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
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
