Difference between revisions of "Undecidable problem"
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) (→See also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 28: | Line 28: | ||
* [[Algorithm]] | * [[Algorithm]] | ||
| + | * [[Decidability (logic)]] | ||
* [[Decision problem]] | * [[Decision problem]] | ||
* [[Entscheidungsproblem]] | * [[Entscheidungsproblem]] | ||
| Line 36: | Line 37: | ||
* [https://en.wikipedia.org/wiki/Undecidable_problem Undecidable problem] @ Wikipedia | * [https://en.wikipedia.org/wiki/Undecidable_problem Undecidable problem] @ Wikipedia | ||
| + | |||
| + | |||
| + | |||
| + | [[Category:Computation]] | ||
| + | [[Category:Computing]] | ||
| + | [[Category:Paradox]] | ||
Latest revision as of 08:41, 13 September 2016
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.
Discussion
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.
These inputs can be natural numbers, but also other values of some other kind, such as strings of a formal language.
Using some encoding, such as a Gödel numbering, the strings can be encoded as natural numbers.
Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers.
To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.
Natural numbers
Formally, a decision problem is a subset of the natural numbers.
The corresponding informal problem is that of deciding whether a given number is in the set. A decision problem A is called decidable or effectively solvable if A is a recursive set.
A problem is called partially decidable, semi-decidable, solvable, or provable if A is a recursively enumerable set. This means that there exists an algorithm that halts eventually when the answer is yes but may run for ever if the answer is no.
Partially decidable problems and any other problems that are not decidable are called undecidable.
See also
External links
- Undecidable problem @ Wikipedia
