Computability
Computability is a fundamental branch of Mathematical-Logic and Theoretical-Computer-Science that explores the limits of what can be calculated by an Algorithm. The discipline emerged in the early 20th century as mathematicians sought to formalize the concept of effective calculability. The Church-Turing-Thesis serves as a foundational bridge, asserting that any function that is intuitively computable can be computed by a Turing-Machine.
Historical Development
The field was shaped by the landmark work of Alan-Turing, who introduced the concept of the universal machine, and Alonzo-Church, who developed the Lambda-Calculus. Simultaneously, Kurt-Gödel contributed through his study of Recursive-Functions and his incompleteness theorems, which demonstrated that certain truths in mathematics are unprovable and, by extension, certain problems are beyond the reach of computation.
Decidability and the Halting Problem
A central question in Computability-Theory is whether a problem is Decidable. A problem is decidable if there exists an algorithm that provides a 'yes' or 'no' answer for every input in a finite amount of time. The most famous example of Undecidability is the Halting-Problem, which proves that no algorithm can determine, for any arbitrary program and input, whether the program will eventually stop or run forever. This result, established by Alan-Turing, defines the absolute boundaries of mechanical reasoning.
For more detailed information, consult the Stanford Encyclopedia of Philosophy or the Wikipedia entry on Computability Theory.