This HTML5 document contains 93 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-cahttp://ca.dbpedia.org/resource/
n13https://www.researchgate.net/profile/Albert_Meyer/publication/234810406_The_complexity_of_loop_programs/links/
n12https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-hrhttp://hr.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Decider_(Turing_machine)
rdf:type
owl:Thing
rdfs:label
Máquina de Turing que sempre para Decider (Turing machine) Macchina che termina sempre Màquina que sempre s'atura 判定器
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. 在可计算性理论中，总是停机的机器也叫做判定器（Sipser，1996年）或全图灵机（Kozen，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。 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. 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. 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.
rdfs:seeAlso
dbr:Termination_analysis
dcterms:subject
dbc:Turing_machine
dbo:wikiPageID
1352564
dbo:wikiPageRevisionID
1099615127
dbo:wikiPageWikiLink
dbr:Kleene's_recursion_theorem dbr:Ackermann_function dbr:Albert_R._Meyer dbr:BlooP_and_FlooP dbr:Michael_Sipser dbr:Consistent dbr:Total_function dbr:BASIC dbr:Dennis_Ritchie dbr:Computability_theory dbr:Soundness dbr:Term_rewriting dbr:Halting_problem dbr:Lawrence_Landweber dbr:Recursively_enumerable dbr:First-order_logic dbr:Recursive_language dbr:Decision_tree dbr:Infinite_loop dbr:Toy_programming_language dbr:Goodstein_sequence dbc:Turing_machine dbr:Gödel's_incompleteness_theorems dbr:Decision_problem dbr:Well-order dbr:Total_recursive_function dbr:Peano_arithmetic dbr:Control_flow dbr:Partial_functions dbr:Primitive_recursive_functions dbr:Formal_language dbr:Dexter_Kozen dbr:Turing_machine dbr:Introduction_to_the_Theory_of_Computation dbr:Total_functional_programming dbr:Arithmetical_hierarchy dbr:Termination_analysis dbr:Undecidable_problem
dbo:wikiPageExternalLink
n13:00b49517fb0c8b6a2a000000.pdf
owl:sameAs
dbpedia-ca:Màquina_que_sempre_s'atura dbpedia-fa:ماشین_تورینگ_کامل n12:2NGeP dbpedia-it:Macchina_che_termina_sempre dbpedia-hr:Stroj_koji_uvijek_staje dbpedia-sr:Машина_која_увек_стаје dbpedia-pt:Máquina_de_Turing_que_sempre_para wikidata:Q2518389 dbpedia-zh:判定器
dbp:wikiPageUsesTemplate
dbt:Math_theorem dbt:Main_article dbt:Clarify_span dbt:Formal_languages_and_grammars dbt:Val dbt:Tmath dbt:Mvar dbt:See_also dbt:Short_description
dbo:abstract
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. 在可计算性理论中，总是停机的机器也叫做判定器（Sipser，1996年）或全图灵机（Kozen，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。 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. 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. 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.
prov:wasDerivedFrom
wikipedia-en:Decider_(Turing_machine)?oldid=1099615127&ns=0
dbo:wikiPageLength
8921
foaf:isPrimaryTopicOf
wikipedia-en:Decider_(Turing_machine)
Subject Item
dbr:Decider_Turing_machine
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageRedirects
dbr:Decider_(Turing_machine)
Subject Item
dbr:Total_Turing_machine
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageRedirects
dbr:Decider_(Turing_machine)
Subject Item
dbr:Machine_that_always_halts
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageRedirects
dbr:Decider_(Turing_machine)
Subject Item
dbr:Decider
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageDisambiguates
dbr:Decider_(Turing_machine)
Subject Item
dbr:Machines_that_always_halt
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageRedirects
dbr:Decider_(Turing_machine)
Subject Item
dbr:Decider_(computability_theory)
dbo:wikiPageWikiLink
dbr:Decider_(Turing_machine)
dbo:wikiPageRedirects
dbr:Decider_(Turing_machine)
Subject Item
wikipedia-en:Decider_(Turing_machine)
foaf:primaryTopic
dbr:Decider_(Turing_machine)