{tag=Undecidable problem}
{wiki}

The canonical <undecidable problem>.


Halting problem

{c}
{tag=Undecidable problem}
{tag=Hilbert's problems}
{title2=1970}
{wiki}

= Determine if one Diophantine equation has a solution
{synonym}
{title2}

Once you hear about the <uncomputability> of such problems, it makes you see that all <Diophantine equation> questions risk being <undecidable>, though in some simpler cases we manage to come up with answers. The feeling is similar to watching people trying to solve the <Halting problem>, e.g. in the effort to determine <BB(5)>.


Hilbert's tenth problem

{tag=Undecidable problem}

= Undecidable Diophantine equation problems
{synonym}

https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/103415#103415 provides a specific single undecidable <Diophantine equation>.


Undecidable Diophantine equation example

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


Ciro Santilli @cirosantilli 37

 Tagged: Undecidable problem