An Entity of Type: disease, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
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
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License