What is Computable?

Mathematical Logic · Axiom Academy

Discover which problems can be solved by algorithms—and which are provably impossible. Let's start with the intuitive idea of an algorithm. Try running this simple "doubling algorithm" with different inputs. Many problems can be solved by algorithms. Here are some examples—click on each to see the algorithm in action. Here's a shocking discovery: some problems are provably impossible to solve. Consider the Halting Problem: "Does this program halt or run forever?" Given a program P and an input I, determine: Will P(I) eventually halt, or will it run forever? Alan Turing proved in 1936 that no algorithm can solve the halting problem for all possible programs. This isn't just hard—it's impossible . Try to classify these problems: which are computable (can be solved by an algorithm) and which are non-computable (provably impossible)? Drag these problems to the correct category: Computability theory asks: "Which problems can be solved by algorithms?" It turns out there are precise mathematical boundaries between what's possible and what's not. These can be solved by algorithms that always halt with the correct answer. Examples: sorting, searching, arithmetic, testing properties of finite objects. These are provably impossible to solve by any algorithm. The halting problem is the most famous example, but there are infinitely many others!

This is the written version of the interactive lesson above. See the full Mathematical Logic course.