Next | Topology of Data Types | 4 |

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

Post Correspondence Problem

Wang Tilings

continued...

Next