Halting problem

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 (i.e., halt) 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. 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 of not solvable is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly. Informally, 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. Jack Copeland (2004) attributes the introduction of the term halting problem to the work of Martin Davis in the 1950s.

Words

This table shows the example usage of word lists for keywords extraction from the text above.

WordWord FrequencyNumber of ArticlesRelevance
halting63230.277
problem7138170.199
turing36090.13
program6736000.123
turing's2520.11

This website uses cookies to ensure you get the best experience on our website. Learn more. Got it.