Open Problems Atlas Atlas Glossary Lab About
← Glossary

Undecidability

Foundations and logic

In computability, the property of a decision problem for which no algorithm always halts with a correct answer. In logic, a statement is undecidable in a theory when neither it nor its negation is provable from its axioms.

What is usually left out

These are two different notions sharing a word, and confusing them is common. The halting problem is undecidable in the first sense: no program can correctly decide, for all inputs, whether a given program halts. The continuum hypothesis is undecidable in the second sense, relative to ZFC. The first is about algorithms, the second about axioms.

Related terms