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 |