Undecidability

• 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?