Dictionary De - En
De - Es
De - Pt| English Dictionary: computability theory | by the DICT Development Group |
| 1 result for computability theory | |
| From The Free On-line Dictionary of Computing (15Feb98) [foldoc]: | |
|
computability theory 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) | |
