Computable and non-computable functions
Functions computable by algorithms versus functions without computing procedures. Computability connects to Turing machines: Turing-computable functions are computable by algorithms. Most functions are non-computable.
Real World
The Busy Beaver function, which calculates the maximum output an n-state Turing machine can produce, grows faster than any computable function — in 2024, researchers finally proved that BB(5) = 47,176,870, a result requiring years of collaborative effort.
Exam Focus
Link non-computability to the halting problem — explain that if a function were computable, it would solve a known undecidable problem.
How well did you know this?