The mid to late 1930s saw the publication of two complementary landmark papers in the early history of computer science. One lays the theoretical groundwork for computers as general-purpose solvers of any algorithm. The other proposes the application of electronic (relay) circuits to problems of symbolic logic.
In his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, English mathematician Alan Mathison Turing introduced the concept of a simple, hypothetical “automatic machine”, later named a (universal) Turing machine. He proved such a machine to be capable of computing anything that is computable, using only a read/write head performing elementary operations (read, write, move) over an infinite memory, governed by strictly following a set of atomic rules. Since Turing showed that all computable algorithms can be reduced to such a set of rules for his conceptual machines, they serve as the basic theoretical model for a digital general-purpose computer—the ultimate hypothetical computing machine. Such machines are said to be Turing-complete, a label that applies to all modern computers.
Turing applied these ideas to show that there can be no general solution to the Entscheidungsproblem, which asks for an algorithm that can determine truth or falsity of any mathematical statement. He did so by showing that his conceptual machines are not able to solve the equivalent halting problem, which asks for an automatic machine to determine whether any other automatic machine, given its program (i.e. set of rules), will ever terminate. (The gist of it: in order to examine the machine and program to be tested, the testing machine would essentially need to emulate, or re-enact, all the steps it performs—so, if the process being examined never reaches a conclusion, neither will the process that examines it.)
These important theoretical results, and their very practical applications to the design of digital computers and programming languages, have earned Alan Turing the honourable title of “father of computer science”. Interestingly, few people recognised the importance of the work at the time of its publication. The Turing Award, the so-called “Nobel Prize of computing”, is named in his honour, and awarded annually to the most influential computer scientists.
In 1937, at the Massachusetts Institute of Technology (MIT), Claude Elwood Shannon completed his master’s thesis, of which a portion was published as a paper entitled A Symbolic Analysis of Relay and Switching Circuits in 1938. In it, Shannon proposed to consider relay switching networks as Boolean expressions, where open and closed relays represented Boolean values of 0 and 1, respectively. Boolean algebra could then be used to simplify existing arrangements, or find the most efficient implementation of new requirements. However, this is overshadowed by the implications of the reverse operation: modelling Boolean expressions as networks of relays, which could then be used to solve logic problems. This is the foundation of digital circuit design, and by extension all of electronic digital computing.
The same principle was already described two years prior, in a 1935 thesis by Russian electrical engineer Victor Shestakov. However, Shestakov’s work was not published until 1941, so the credit for creating a sound theoretical basis for digital circuit design went to Shannon instead. Experimental designs in digital circuitry had been realised earlier, but in a rather limited and ad hoc fasion. Shannon’s way of thinking paved the way for more complex logic circuits, translated to vacuum tubes and transistors, eventually leading to today’s incredibly complex integrated circuits (ICs).
Shannon continued to expand on his ideas, earning the title “father of information theory” by almost single-handedly creating the eponymous new field of science with the publication of another paper in 1948 (a separate article on the topic will follow).
Alan Turing and Claude Shannon knew each other, having met and exchanged ideas on numerous occasions.
« Return to Part I — Prehistory
References
- Wikipedia: Alan Turing, Turing machine, Turing Award
- Wikipedia: Claude Shannon, Shannon’s paper
- Portrait of Alan Turing: MacTutor History of Mathematics
- Portrait of Claude Shannon: MacTutor History of Mathematics
