Next | Topology of Data Types | 5 |

Turing (1936) and Post (1936) discovered that not all problems are decidable

Fundamental example:

Given a computer program *p*

and an input *i*,

will *p* halt when run on input *i*?

Related examples:

Matching and tiling problems that somehow embed all the complexity of program execution

Numerical problems that somehow embed all the complexity of program execution

Mathematical example:

Given a diophantine equation,

does it have a solution?

(That's Hilbert's 10th problem)

Next