Turing's proof

In November 1936, Alan Turing published a landmark paper titled "On Computable Numbers, with an Application to the Entscheidungsproblem." This work addressed a major challenge posed by mathematician David Hilbert. Hilbert conjectured that all mathematical yes-no questions could eventually be answered through computation. Turing's proof provided the negation of this conjecture. He demonstrated that certain decision problems are undecidable. An undecidable problem is one where no single algorithm can infallibly provide a correct "yes" or "no" answer for every instance.

Turing's approach relied on the concept of computing machines. These machines follow a simple set of rules to process information. He developed the idea of a "universal computing machine" to expand these possibilities. To prove his points, Turing used a method called reductio ad absurdum. This is a form of proof where you assume a premise is true and show it leads to an impossible contradiction. Turing spent much of his paper constructing these machines to make his logic feel concrete and buildable.

The first part of his work focused on a specific type of machine. He imagined a "decision machine" called D. This machine would take a Standard Description (S.D.), which is a string of symbols like A, C, D, L, R, or N. Machine D would then decide if that description represented a "satisfactory" or "unsatisfactory" machine. A machine was considered satisfactory if it was "circle-free," meaning it would print its binary numbers forever. If it entered a loop or stopped, it was unsatisfactory.

Turing then described a machine called H to test this idea. Machine H contains the decision machine D as a subroutine. H converts numbers into symbol strings for D to test. It also keeps a tally, which he called R, of all the successful machines it finds. As H runs, it prints a "diagonal number" called B' onto its tape. H creates this number by simulating the motions of each satisfactory machine. It waits until a machine reaches its Rth figure, such as a 1 or a 0, and then prints that figure.

The logical collapse happens when machine H attempts to process its own number, K. If H reaches its own number, it must simulate itself. This creates a recursive loop where the machine is essentially running its own instructions. If H is supposed to be a satisfactory, circle-free machine, it must print its diagonal number forever. However, the simulation of itself prevents it from ever reaching the next figure in the sequence. This contradiction proves that the initial decision machine D cannot actually exist.

Turing provided a second proof that is often recognized as Rice's theorem. This proof explores whether a machine E can determine if another machine M will ever print a specific symbol, such as 0. Turing showed that if such a machine E existed, one could build a machine to determine if any machine is circle-free. Since he already proved that no machine can decide if a machine is circle-free, machine E must also be impossible. He achieved this by converting individual statements about machines into a single, collective string of information.

His third proof connected these ideas back to formal logic. He showed that if there were a general method to determine if a specific formula is provable, there would be a way to know if a machine ever prints a 0. This linked the mechanical behavior of machines directly to the limits of mathematical proof. In only 64 words and symbols, Turing used these steps to conclude that the Hilbert Entscheidungsproblem has no solution. His work established that the boundaries of computation are fixed by logic itself.