computability theory
<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)
Nearby terms:
CompuServe Corporation « CompuServe Information
Service « Compusult Ltd. « computability theory
» computable » Computational Adequacy Theorem »
computational complexity
|
