{wiki}

Subset of <recursively enumerable language> as explained at: <difference between recursive language and recursively enumerable language>.


Recursive language

{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>


Undecidable problem

{tag=Chomsky hierarchy}
{wiki}

There is a <Turing machine> that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.

Non-examples: https://cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages


Ciro Santilli @cirosantilli 37

 Incoming links: Recursively enumerable language