Entscheidungsproblem
Turing proposes a computer program that can determine for certain if any program fed into it will halt or not. He also proposes another program that halts if the input is loop, and loops if the input is halt. He says to make these two programs one new program. Then, he proposes to feed this new program's code into itself. This means the program thinks it will halt, so it will loop, but then it'll loop, so it'll halt, and so on and so forth. This is a paradox, which means for certain that you cannot write a program to determine if every program will halt or not.