Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Undecidable problem
open-in-new
<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a> and <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, an undecidable problem is a <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> for which it is proved to be impossible to construct an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that always leads to a correct yes-or-no answer. The <a href="/facts/Halting_problem/Xz1bac40">halting problem</a> is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run. </p>