The Limits of Computation
ver. 1.0.0, limits_of_computation
How to define decision problems, what decidability means, why not all logical assertions are decidable, and what a proof of undecidability requires
This unit teaches how to define decision problems and instances, gives an informal account of decidability (a program that always halts and answers correctly), shows how to express decision problems in predicate logic, demonstrates that first-order-expressible problems need not be decidable using Gödelian and Diophantine examples, and explains that proving undecidability requires a precise mathematical model of “algorithm.”
Learners will be able to distinguish a general problem from a specific instance of it and to give a precise definition of a decision problem (a boolean-valued function on instances, equivalently membership in a set). They will understand decidability intuitively: a decision problem is decidable if there exists a program that always halts and always gives the correct yes/no answer. Using primality as a running example, learners will practice writing decision problems both as functions and as set-membership questions and will translate such problems into the language of predicate logic (quantifiers, connectives, and arithmetic symbols), verifying that the formal statement matches the informal intent.
The unit states clearly that not every assertion expressible in first-order logic is mechanically decidable: the answer to Hilbert’s Entscheidungsproblem is no. Two concrete witnesses illustrate this impossibility: Gödel-style self-referential constructions that produce true-but-unprovable statements in sufficiently expressive systems, and Matiyasevich’s result about Diophantine equations showing there is no general algorithm to decide solvability of arbitrary polynomial equations in integers. Finally, learners are led to the key conceptual gap that remains for a rigorous undecidability proof: the informal claim “no algorithm exists” quantifies over every possible algorithm, so a proof needs a precise mathematical object that captures what an “algorithm” is. The next step (in the following module) is to introduce that formal model so undecidability statements can be made and proved rigorously.
Materials
Source document
- Course material, Ken Pu