Computability Theory

If a problem is computable, is can be solved via the use of a computer, and if it is non-computable, it cannot be. However, it is not always as clean cut as 'can' and 'can't' be solved - many non-computable problems have partial or approximate solutions that can be gotten using a computer.

Computability theory, also known as recursion theory, came about along with the rise of the computer. The field originally sprung from several research-orientated, but also philosophically interesting, questions such as:

What does it mean for natural numbers to be computable?
How can non-computable problems be classified by their level of non-computability (e.g. partial solutions, approximate solutions, etc.)?

Often these kinds of questions are not the sort that yield single, resounding answers quickly, so the field is still developing and growing today.

In general, problems in computability theory are called functions and often written out in pseudocode to aid understanding. The most useful tool in a computability theorist's pocket is the Church-Turing Hypothesis which decrees that if a function is computable by an algorithm, it is computable. This means they need only find an algorithm that can definitively solve a problem to call it computable - however, this is often easier said than done.

BrainMass