|Next||Topology of Data Types||4|
Turing (1936) and Post (1936) discovered that not all problems are decidable
Given a computer program p and an input i, will p halt when run on input i?
Matching and tiling problems that somehow embed all the complexity of program execution
Post Correspondence Problem