In 1937 Alan Turing published his famous paper on computability. In the paper he expanded on Kurt Gödel’s work on the Entscheidungsproblem (decision problem). The Entscheidungsproblem is the question, “Can any mathematical problem be solved?” Gödel proved that there are problems that cannot be solved, which was a big deal because most mathematicians assumed the opposite was true. Turing and separately another mathematician named Alonzo Church, proved that not only are there problems that cannot be solved, but that it is not possible to build a universal algorithm to determine which problems can or cannot be solved.
A side effect of Turing’s famous paper was The Turing Machine. In the paper Turing described a machine that ran on a tape, entering zeros and ones to compute problems. Generalized his description of this early computer is any computer in use today with a processor and memory (what you are using to read this).
A Turing Machine enthusiast name Mike Davey has built a real, working Turing machine. Here is the video:
