The Boundary Between Man and God

The Continuum Problem was Hilbert's First Problem. Another concerned decidability.

Within a finite amount of time, was it always possible to find a step-by-step procedure to determine whether a given mathematical proposition was true or false?

Gödel's Incompleteness Theorem shattered this notion of decidability.

It proved that in any logically consistent axiomatic system large enough to encompass all rules of computation, there would always be mathematical facts that could not be proven.

Yet Gödel's Incompleteness Theorem still left a door open regarding whether mathematical propositions could be proven.

Although every self-consistent axiomatic system contained mathematical facts that could not be proven, could a series of steps or an algorithm be found to determine whether any given mathematical proposition was provable?

Just as Gödel had done when proving the Incompleteness Theorem—proving that a mathematical proposition was unprovable.

It was Turing and the Halting Problem of the Turing Machine that closed this door.

There was no universal algorithm capable of determining whether every input would eventually halt. Hilbert's decision problem could not be solved.

No matter how ingenious a program was, it could never calculate whether other programs would terminate under all circumstances.

Many mathematical facts were not merely unprovable; it was impossible even to determine whether they could be proven.

These problems were known as undecidable problems.

In mathematics, the difficulty of proving propositions was divided into several levels.

Some propositions had short axiomatic proofs, concise and elegant.

Propositions proven before the advent of modern computers all belonged to this category, and they were also the sort of proofs most people knew.

Some propositions had no short axiomatic proof, but did have short proofs when computation was employed, such as the Four Color Theorem.

Some propositions still had only lengthy proofs even with computation, making it impossible to write out the