资料来源 : Free On-Line Dictionary of Computing

computability theory
     
         The area of theoretical computer science
        concerning what problems can be solved by any computer.
     
        A function is computable if an {algorithm} can be implemented
        which will give the correct output for any valid input.
     
        Since computer programs are {countable} but {real numbers} are
        not, it follows that there must exist real numbers that
        cannot be calculated by any program.  Unfortunately, by
        definition, there isn't an easy way of describing any of them!
     
        In fact, there are many tasks (not just calculating real
        numbers) that computers cannot perform.  The most well-known
        is the {halting problem}, the {busy beaver} problem is less
        famous but just as fascinating.
     
        ["Computability", N.J. Cutland. (A well written
        undergraduate-level introduction to the subject)].
     
        ["The Turing Omnibus", A.K. Dewdeney].
     
        (1995-01-13)