Mortality (computability theory) (original) (raw)
In computability theory, the mortality problem is a decision problem which can be stated as follows: Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a starting one) Philip K. Hooper proved in 1966 that the mortality problem is undecidable. However, it can be shown that the set of Turing machines which are mortal (i.e. halt on every starting configuration) is recursively enumerable. * v * t * e
| Property | Value |
|---|---|
| dbo:abstract | In computability theory, the mortality problem is a decision problem which can be stated as follows: Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a starting one) In the statement above, the configuration is a pair , where q is one of the machine's states (not necessarily its initial state) and w is an infinite sequence of symbols representing the initial content of the tape. Note that while we usually assume that in the starting configuration all but finitely many cells on the tape are blanks, in the mortality problem the tape can have arbitrary content, including infinitely many non-blank symbols written on it. Philip K. Hooper proved in 1966 that the mortality problem is undecidable. However, it can be shown that the set of Turing machines which are mortal (i.e. halt on every starting configuration) is recursively enumerable. * v * t * e (en) Na teoria da computabilidade, o problema da mortalidade é um problema de decisão que pode ser enunciado como segue: Dada uma máquina de Turing, decidir se pára quando executada em uma configuração qualquer (não necessariamente uma configuração inicial) Na declaração acima, a configuração é um par , onde q é um dos estados da máquina (não necessariamente seu estado inicial) e w é uma sequência infinita de símbolos que representam o conteúdo inicial da fita. Note-se que enquanto geralmente assumimos que na configuração inicial quase todo número finito de células na fita são espaços em branco, no problema da mortalidade a fita pode ter conteúdo arbitrário, incluindo um número infinito de símbolos que não estão com o símbolo "em branco" escrito nela. Philip K. Hooper provou em 1966 que o problema da mortalidade é indecidível. No entanto, pode-se mostrar que o conjunto de máquinas de Turing que são mortais (ou seja, que param em todas as configurações iniciais) é recursivamente enumerável. (pt) |
| dbo:wikiPageID | 10646392 (xsd:integer) |
| dbo:wikiPageLength | 1102 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1090784838 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decision_problem dbr:Computability_theory dbc:Undecidable_problems dbr:Recursively_enumerable dbc:Theory_of_computation dbr:Turing_machine dbr:Undecidable_problem |
| dbp:wikiPageUsesTemplate | dbt:Comp-sci-stub dbt:Not_a_typo dbt:Unreferenced |
| dct:subject | dbc:Undecidable_problems dbc:Theory_of_computation |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | In computability theory, the mortality problem is a decision problem which can be stated as follows: Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a starting one) Philip K. Hooper proved in 1966 that the mortality problem is undecidable. However, it can be shown that the set of Turing machines which are mortal (i.e. halt on every starting configuration) is recursively enumerable. * v * t * e (en) Na teoria da computabilidade, o problema da mortalidade é um problema de decisão que pode ser enunciado como segue: Dada uma máquina de Turing, decidir se pára quando executada em uma configuração qualquer (não necessariamente uma configuração inicial) Philip K. Hooper provou em 1966 que o problema da mortalidade é indecidível. No entanto, pode-se mostrar que o conjunto de máquinas de Turing que são mortais (ou seja, que param em todas as configurações iniciais) é recursivamente enumerável. (pt) |
| rdfs:label | Mortality (computability theory) (en) Mortalidade (teoria da computabilidade) (pt) |
| owl:sameAs | freebase:Mortality (computability theory) wikidata:Mortality (computability theory) dbpedia-pt:Mortality (computability theory) https://global.dbpedia.org/id/4rZXe |
| prov:wasDerivedFrom | wikipedia-en:Mortality_(computability_theory)?oldid=1090784838&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Mortality_(computability_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Mortality |
| is dbo:wikiPageWikiLink of | dbr:Mortality dbr:Recursively_enumerable_language dbr:List_of_undecidable_problems |
| is foaf:primaryTopic of | wikipedia-en:Mortality_(computability_theory) |