Computability
The study of what problems can be solved by computational processes and which are fundamentally unsolvable. Computable functions are those calculable by algorithms. Uncomputable functions are provably unsolvable by any algorithm. Understanding computability limits clarifies achievable and unachievable goals.
Real World
Antivirus software like Norton cannot guarantee detection of every possible virus, because determining whether arbitrary code is malicious is equivalent to solving the halting problem — so companies rely on signature databases and heuristics instead.
Exam Focus
State the Church-Turing thesis precisely — it is a thesis (not a theorem) asserting equivalence between algorithms and Turing-computable functions.
How well did you know this?