Decidable and Undecidable Problems

Every algorithm is a step by step procedure that's supposed to finish and give an answer. For a decidable problem, you can write a program that takes any valid input, runs for a finite amount of time, and always halts with the correct yes or no answer. Checking whether a number is even, whether a list is sorted, or whether a graph has a path between two cities are all decidable: a correct, general algorithm exists for each, and it terminates every time. Undecidable problems are different in kind, not just in difficulty. For these, it has been mathematically proven that no algorithm, however clever or however much time and memory it's given, can correctly answer every instance. The most famous example is the halting problem: given an arbitrary program and its input, decide whether that program will eventually halt or run forever. No general algorithm for this can ever exist, and that has been proven, not just observed.

This sits at the edge of what Big Idea 3 has been building toward. Variables, branches, loops, lists, and procedures let you build algorithms that solve enormous classes of problems efficiently or at least eventually. Decidability asks a more basic question first: before worrying about speed, does any correct general algorithm exist at all? Undecidability marks a hard boundary on computation itself, separate from runtime concerns like how long a working algorithm takes to finish.