= Undecidable problem
{tag=Decision problem}
{wiki}
= Undecidable
{synonym}
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.
* https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics
* https://en.wikipedia.org/wiki/List_of_undecidable_problems
Coolest ones besides the obvious boring <halting problem>:
* <mortal matrix problem>
* <Diophantine equation> existence of solutions: <undecidable Diophantine equation problems>
Back to article page