computable

computable
    adj 1: may be computed or estimated; "a calculable risk";
           "computable odds"; "estimable assets" [syn: {computable},
           {estimable}]
    

Computable \Com*put"a*ble\, a. [L. computabilis.]
   Capable of being computed, numbered, or reckoned.
   [1913 Webster]

         Not easily computable by arithmetic.     --Sir M. Hale.
   [1913 Webster]
    

computability theory
computable

   <mathematics> 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)