Incoming links: Decision problem
A:
- decidable problem is to a decision problem
- like a computable problem is to a function problem
A problem that has more than two possible yes/no outputs.
It is therefore a generalization of a decision problem.
Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.
Is a decision problem of determining if something belongs to a non-recursive language.
Or in other words: there is no Turing machine that always halts for every input with the yes/no output.
Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.
Some undecidable problems are of recursively enumerable language, e.g. the halting problem.
Lists of undecidable problems.
Coolest ones besides the obvious boring halting problem:
- mortal matrix problem
- Diophantine equation existence of solutions: undecidable Diophantine equation problems