Skip to content

Latest commit

 

History

History
13 lines (7 loc) · 680 Bytes

undecidability.md

File metadata and controls

13 lines (7 loc) · 680 Bytes

Undecidability

http://en.wikipedia.org/wiki/Undecidable_problem

It can be proved that for certain problems, there is no Turing machine (and therefore any algorithm) that solves its instances.

Cool examples of such problems:

  • halting problem. First discovered example. Proof of undecidability via cantors diagonal method.

There may however be Turing machines which solve specific families of instances, but there cannot be a finite number of such Turing machines that solve all problems, otherwise we could just run them all in parallel until one of them halts.

Those problems are called undecidable, and trying to solve them general is impossible with Turing machines.