He used his formalism to show that the Hilbert Entscheidungsproblem had no solution-in other words, that it is possible to state mathematical propositions whose attempted proofs never terminate. When he presented his paper, Turing was completely unknown in the field of mathematical logic. Turing showed that such a machine was capable of proving anything that could be proved by more complicated formalisms. A set of rules (what we would today call its program) would cause the machine to read a single zero or one from the tape, then possibly erase it and write a new symbol in its place, move the tape one position to the left or right, and transition to a new state. This machine had a finite number of states and an infinite tape containing a finite, but unlimited, number of zeros and ones. Turing formalized the notion of proof by introducing a theoretical machine. Hilbert challenged mathematicians to formalize the notion of mathematical proof and determine whether it is possible to state a proposition that can be neither proved nor disproved. In 1936, as a 24-year-old student at King’s College, Cambridge, Turing delivered a paper that was to become the foundation of modern-day computer science: “On Computable Numbers, with an Application to the Entscheidungsproblem.” Loosely stated, the Entscheidungsproblem, or Halting Problem, asks “Is it possible to begin a proof that never finishes?” The question was first posed in 1928 by the great German mathematician David Hilbert.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |