본문 바로가기

자료구조 및 알고리즘

Undecidable problem

From: (위키피디아) http://en.wikipedia.org/wiki/Undecidable_problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer — the problem is not decidable.

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.