halting problem

The problem of determining in advance whether a particularprogram or algorithm will terminate or run forever. Thehalting problem is the canonical example of a provably unsolvable problem. Obviously any attempt to answer thequestion by actually executing the algorithm or simulatingeach step of its execution will only give an answer if thealgorithm under consideration does terminate, otherwise thealgorithm attempting to answer the question will itself runforever.

Some special cases of the halting problem are partiallysolvable given sufficient resources. For example, if it ispossible to record the complete state of the execution of thealgorithm at each step and the current state is ever identicalto some previous state then the algorithm is in a loop. Thismight require an arbitrary amount of storage however.Alternatively, if there are at most N possible differentstates then the algorithm can run for at most N steps withoutlooping.

A program analysis called termination analysis attempts toanswer this question for limited kinds of input algorithm.

单词	halting problem
释义	halting problem halting problem The problem of determining in advance whether a particularprogram or algorithm will terminate or run forever. Thehalting problem is the canonical example of a provably unsolvable problem. Obviously any attempt to answer thequestion by actually executing the algorithm or simulatingeach step of its execution will only give an answer if thealgorithm under consideration does terminate, otherwise thealgorithm attempting to answer the question will itself runforever. Some special cases of the halting problem are partiallysolvable given sufficient resources. For example, if it ispossible to record the complete state of the execution of thealgorithm at each step and the current state is ever identicalto some previous state then the algorithm is in a loop. Thismight require an arbitrary amount of storage however.Alternatively, if there are at most N possible differentstates then the algorithm can run for at most N steps withoutlooping. A program analysis called termination analysis attempts toanswer this question for limited kinds of input algorithm.
随便看	holistic psychology holistic quantum relativity holistic reiki holistic research holistic resources foundation holistic theory holistic therapies holistic therapy holistic understanding for justified research and action holistic veterinary medical association holistic view holistic workout holists holj holjc holk holkar state holkham hall holl holla holla at me holla at ya boy holla bend national wildlife refuge holladay automated contrast sensitivity system holladay, ben