GRAPH NAME FOUNDATIONS OF COMPUTING *** ## NODE 1 NAME BINARY ARITHMETIC DATE 1703 PLACE France - Paris WHO Gottfried Wilhelm Leibniz BRIEF DESCRIPTION Leibniz publishes a formal exposition of binary arithmetic using only the symbols 0 and 1. The binary system would later become a fundamental mathematical representation for digital computers. LINK *** ## NODE 2 NAME JACQUARD LOOM DATE 1804 PLACE France - Lyon WHO Joseph Marie Jacquard BRIEF DESCRIPTION The Jacquard loom uses punched cards to automatically control weaving patterns. Although it was not a computer, it represents an important precursor to the use of externally encoded information to control sequences of machine operations. LINK *** ## NODE 3 NAME DIFFERENCE ENGINE DATE 1822 PLACE United Kingdom - England - London WHO Charles Babbage BRIEF DESCRIPTION Charles Babbage proposes a mechanical machine designed to automatically calculate mathematical tables using finite differences. The project introduces principles of automated calculation that would later evolve into designs for programmable machines. LINK *** ## NODE 4 NAME ANALYTICAL ENGINE DATE 1837 PLACE United Kingdom - England - London WHO Charles Babbage BRIEF DESCRIPTION Babbage develops the conceptual design of a programmable general-purpose mechanical machine. Its architecture included storage, processing, control, and input through punched cards, anticipating functions present in later computers. LINK *** ## NODE 5 NAME LOVELACE ALGORITHM DATE 1843 PLACE United Kingdom - England - London WHO Ada Lovelace BRIEF DESCRIPTION Ada Lovelace publishes notes on the Analytical Engine that include a procedure for calculating Bernoulli numbers. The work constitutes one of the earliest published examples of an algorithm explicitly designed for automatic execution by a machine. LINK *** ## NODE 6 NAME BOOLEAN ALGEBRA DATE 1854 PLACE United Kingdom - England - London WHO George Boole BRIEF DESCRIPTION George Boole publishes An Investigation of the Laws of Thought and develops an algebraic treatment of logical operations. Boolean algebra would later provide mathematical foundations for computational logic and digital circuits. LINK *** ## NODE 7 NAME DECISION PROBLEM DATE 1928 PLACE Germany - Göttingen WHO David Hilbert and Wilhelm Ackermann BRIEF DESCRIPTION The Entscheidungsproblem asks whether a general mechanical procedure exists that can determine the validity of any expression in a given formal logic. The problem plays a central role in the subsequent development of the mathematical theory of computation. LINK *** ## NODE 8 NAME RECURSIVE FUNCTIONS DATE 1934 PLACE USA - New Jersey - Princeton WHO Kurt Gödel and Jacques Herbrand BRIEF DESCRIPTION The development of recursive functions provides one of the earliest mathematical formalizations of effectively calculable procedures. These ideas contribute to the later establishment of equivalent models of computability. LINK *** ## NODE 9 NAME LAMBDA CALCULUS DATE 1936 PLACE USA - New Jersey - Princeton WHO Alonzo Church BRIEF DESCRIPTION Alonzo Church uses lambda calculus to formalize functions and computable procedures and demonstrates the unsolvability of the Entscheidungsproblem. Lambda calculus becomes one of the fundamental models of computation and later influences functional programming languages. LINK *** ## NODE 10 NAME TURING MACHINE DATE 1936 PLACE United Kingdom - England WHO Alan Turing BRIEF DESCRIPTION Alan Turing introduces an abstract machine model capable of executing procedures through rules operating on symbols. The formulation provides an operational definition of computation and makes it possible to demonstrate that some problems cannot be solved by any algorithm. LINK *** ## NODE 11 NAME CHURCH-TURING THESIS DATE 1936 PLACE USA - United Kingdom WHO Alonzo Church and Alan Turing BRIEF DESCRIPTION The models independently developed by Church and Turing characterize the notion of an effectively computable procedure through formalisms equivalent in expressive power. The Church-Turing thesis establishes a correspondence between effective computability and these mathematical models; it is a conceptual thesis rather than a theorem about an informal notion. LINK *** ## NODE 12 NAME LOGICAL CIRCUIT THEORY DATE 1937 PLACE USA - Massachusetts - Cambridge WHO Claude Shannon BRIEF DESCRIPTION Claude Shannon demonstrates that Boolean algebra can be used to represent and simplify electrical switching circuits. The result establishes a direct connection between mathematical logic and the design of digital circuits. LINK *** ## NODE 13 NAME UNIVERSAL COMPUTATION DATE 1937 PLACE USA - New Jersey - Princeton WHO Alan Turing BRIEF DESCRIPTION The universal Turing machine establishes that a single abstract machine can simulate any Turing machine when provided with an appropriate description of that machine and its data. This principle constitutes one of the conceptual foundations of programmable general-purpose computing. LINK *** ## NODE 14 NAME INFORMATION THEORY DATE 1948 PLACE USA WHO Claude Shannon BRIEF DESCRIPTION Claude Shannon formulates a mathematical theory of communication that makes it possible to quantify information through concepts such as entropy and channel capacity. His formalization provides foundations for the representation, encoding, storage, and digital transmission of information. LINK *** ## NODE 15 NAME FINITE AUTOMATA DATE 1956 PLACE USA WHO Stephen Kleene BRIEF DESCRIPTION Work on regular events, regular expressions, and finite automata establishes formal relationships between abstract machines and languages. These concepts become a central part of automata theory and formal language theory. LINK *** ## NODE 16 NAME CHOMSKY HIERARCHY DATE 1956 PLACE USA - Massachusetts WHO Noam Chomsky BRIEF DESCRIPTION Noam Chomsky develops a classification of formal grammars according to their generative capacity. The hierarchy establishes fundamental relationships between classes of languages and abstract models of computation, with later influence on language theory and compilers. LINK *** ## NODE 17 NAME COMPUTATIONAL COMPLEXITY DATE 1965 PLACE USA WHO Juris Hartmanis and Richard Stearns BRIEF DESCRIPTION Hartmanis and Stearns formalize the study of computational complexity by considering the resources required to perform computations. This makes it possible to classify problems not only by their computability but also by the resources required to solve them. LINK *** ## NODE 18 NAME P VERSUS NP PROBLEM DATE 1971 PLACE USA WHO Stephen Cook BRIEF DESCRIPTION Stephen Cook demonstrates that the Boolean satisfiability problem is NP-complete and establishes a formal basis for studying the relationship between problems that can be efficiently verified and problems that can be efficiently solved. This work gives rise to one of the central questions of computational complexity theory. LINK