Undecidable problem
From The Art and Popular Culture Encyclopedia
(Redirected from Undecidablility)
Related e |
Featured: |
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.
[edit]
See also
Unless indicated otherwise, the text in this article is either based on Wikipedia article "Undecidable problem" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.