computability theory

1 definition found

computability theory - Free On-line Dictionary of Computing (26 May 2007) :

  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)