computability theory

Also found in: Dictionary, Thesaurus, Legal, Wikipedia.

computability theory

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].
References in periodicals archive ?
Denmark), while formal epistemology applies a variety of tools and methods from logic, computability theory, or probability theory to the theory of knowledge.
It does this by demonstrating how the theme of reducing abstraction (Hazzan, 1999) can be used for analyzing mental processes of students who learn computability theory.
99]), in the consideration that the classic Computability Theory is not appropriate for that purpose ([Chandra et al.
Computability theory, which defines what machines can and cannot do.
Its intellectual substance goes well beyond the mathematics of numerical analysis, switching theory, computability theory, and programming languages [2].