Entscheidungsproblem

The Entscheidungsproblem (German, "decision problem") is a famous problem of mathematics and computer science. David Hilbert formulated the problem in 1928: Is there an algorithm that will take a formal language, and any logical statement in that language, and that will output "True" or "False", depending on the truth value of the statement? The algorithm does not tell how it reaches the answer, nor prove it, as long as the answer is always correct.

In 1936 and 1937, Alonzo Church and Alan Turing showed independently that no algorithm can satisfy the Entscheidungsproblem. That is, they showed that it is impossible for an algorithm to decide whether certain mathematical statements are true or false.

Turing's Proof

Turing proposes a computer program that can determine if any program given to it will halt. 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.