資料來源 : Free On-Line Dictionary of Computing

halting problem
     
        The problem of determining in advance whether a particular
        program or {algorithm} will terminate or run forever.  The
        halting problem is the {canonical} example of a {provably
        unsolvable} problem.  Obviously any attempt to answer the
        question by actually executing the algorithm or simulating
        each step of its execution will only give an answer if the
        algorithm under consideration does terminate, otherwise the
        algorithm attempting to answer the question will itself run
        forever.
     
        Some special cases of the halting problem are partially
        solvable given sufficient resources.  For example, if it is
        possible to record the complete state of the execution of the
        algorithm at each step and the current state is ever identical
        to some previous state then the algorithm is in a loop.  This
        might require an arbitrary amount of storage however.
        Alternatively, if there are at most N possible different
        states then the algorithm can run for at most N steps without
        looping.
     
        A program analysis called {termination analysis} attempts to
        answer this question for limited kinds of input algorithm.
     
        (1994-10-20)