In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Jack Copeland (2004) attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s.

Property Value
dbo:abstract
  • In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. Turing's proof is one of the first cases of decision problems to be concluded. The theoretical conclusion that it is not solvable is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly. Jack Copeland (2004) attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s. (en)
dbo:wikiPageEditLink
dbo:wikiPageExternalLink
dbo:wikiPageExtracted
  • 2019-09-08 13:19:15Z (xsd:date)
dbo:wikiPageHistoryLink
dbo:wikiPageID
  • 21391870 (xsd:integer)
dbo:wikiPageLength
  • 41324 (xsd:integer)
dbo:wikiPageModified
  • 2019-09-08 13:19:09Z (xsd:date)
dbo:wikiPageOutDegree
  • 155 (xsd:integer)
dbo:wikiPageRevisionID
  • 914626580 (xsd:integer)
dbo:wikiPageRevisionLink
dbp:wikiPageUsesTemplate
dct:subject
rdf:type
rdfs:comment
  • In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Jack Copeland (2004) attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s. (en)
rdfs:label
  • Halting problem (en)
rdfs:seeAlso
owl:sameAs
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is rdfs:seeAlso of
is foaf:primaryTopic of