halting problem
halting problem A decision problem that was discovered and investigated by Alan Turing in 1936. Suppose M is a Turing machine and let x be an input to M. If we start the machine running two things might happen: after a finite number of steps the machine might stop, or it might run on forever. Is there any way to test, given M and x, which of these two situations will occur? This is the halting problem. In fact there is no algorithm or effective procedure that, given any Turing machine and its input, will decide whether or not the calculation ever terminates.
Assuming the Church–Turing thesis, the halting problem is algorithmically unsolvable or undecidable. It is one example of many unsolvable problems in mathematics and computer science. It has profound practical implications: if it were solvable it would be possible to write a program tester that, given (say) any Pascal program and its input, would print “yes” if the program terminated after a finite number of steps and “no” if it did not. For any programming language that can define the recursive functions, no such termination program exists.
Assuming the Church–Turing thesis, the halting problem is algorithmically unsolvable or undecidable. It is one example of many unsolvable problems in mathematics and computer science. It has profound practical implications: if it were solvable it would be possible to write a program tester that, given (say) any Pascal program and its input, would print “yes” if the program terminated after a finite number of steps and “no” if it did not. For any programming language that can define the recursive functions, no such termination program exists.
More From encyclopedia.com
Turing Machine , British mathematician Alan Turing (1912–1954) described what became known as the "Turing Machine" in his 1936 paper, "On Computable Numbers, with an… Automation , Automation is the use of scientific and technological principles in the manufacture of machines that take over work normally done by humans. This def… Parallel Processing , Parallel processing is information processing that uses more than one computer processor simultaneously to perform work on a problem. This should not… Problem Solving , A managerial problem can be described as the gap between a given current state of affairs and a future desired state. Problem solving may then be tho… Sewing Machine , Background
Before 1900, women spent many of their daylight hours sewing clothes for themselves and their families by hand. Women also formed the majo… Computer Program , pro·gram / ˈprōˌgram; -grəm/ (Brit. pro·gramme) • n. 1. a planned series of future events, items, or performances: a weekly program of films the prog…
You Might Also Like
NEARBY TERMS
halting problem