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)