✓ History of Computation¶
Mechanical Devices¶
Babbage Analytical Engine¶
Charles Babbage
Invented one of the first mechanical computers
Costed £17,000, not fully completed as the British Treasury lost confidence after 10 years.
The goal was to compute polynomial functions
Lovelace tabulation¶
Ada Lovelace
Recognized the potential of Babbage’s analytical engine, and its far reaching consequences.
[The Analytical Engine] might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine…Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.
– Countess of Lovelace Augusta Ada King
This is the fundamental concept behind music synthesis using deep learning.
Developed one of the first algorithms for the analytical engine to compute the Bernoulli number sequence.
Birth of computation¶
David Hilbert, 1861 - 1943¶
As one of the greatest mathematicians of his time, Hilbert posed many open problems for the community to consider.
Entscheidungsproblem (1928): can a mechanical device settle all yes/no mathematical statements?
Hilbert’s 10th problem (1900): is their a procedure to solve integer based polynomial equations (Diophantine equations)?
Kurt Gödel, 1906 - 1978¶
In 1931, Godel published the celebrated Godel’s incompleteness theorem. It showed that mechanical procedures cannot prove all truths about natural number arithmetics.
The incomplete theorem completely changed the perspective of the Entscheidungsproblem. Natural numbers with \((+,\times)\) can generate truth statements that can never be reached by procedurally mechanical proofs. But what about computation?
What is a specific example of such unreachable / unprovable problems in \((\mathbb{N}, +, \times)\)?
Spoiler alert: Diophantine equations
Alan Turing, 1912 - 1954¶
In 1936, Turing reformulated Godel’s incomplete theorem using a formal computing device, later known as the Turing Machine. Turing’s result shows that no computational device can ever reach the proofs of a certain class of mathematical problems.
Turing constructed a Universal Turing Machine, a very special Turing Machine that is capable of performing any computation based on algorithms expressed as code. This is the gensis of programming languages.
A special version of Turing Machine was built in 1939 - 1941 during World War II in Bletchley Park. It was to perform cryptanalysis of Nazi’s Enigma encrypted messages.
Alonzo Church, 1903 - 1995¶
He invented a system for formal mathematical reasoning, known as Lambda Calculus, written -Calculus.
Lambda Calculus captures computation using a system of string rewriting over expressions. It turns out that Calculus is equivalent to Turing Machine.
Church published the first paper to directly invalidate Hilbert’s Enscheidungsproblem hypothesis.
John von Neumann, 1903 - 1957¶
Arguably the most productive mathematician, physicist and scientific politician of the 20th century.
Designed one of the first electronic computers based on Turing’s specification.
Modern day computers are known as the von Neumann’s architecture.
von Neumann did not believe the need for programming languages.
Imperative Programming¶
John Backus, 1924 - 2007¶
1954: Invented the first major programming language FORTRAN (formula transation) 1958: Invented the highly influential programming language ALGOL 1959: Co-invented the formal language specification metalanguage known as BNF (Backus-Naur form)
Brian Kernighan, 1942- (Canadian)¶
Born in Toronto, Ontario.
BSc in Engineering Physics at U of Toronto
PhD in Electrical Engineering at Princeton University
1972: invention of the C programming language with Denis Ritchie at AT&T Lab. C is heavily influenced by ALGO60 in code structure and function calls.
Alan Kay, 1940-¶
Bachelor in Molecular Biology in 1966, University of Colorado Boulder
PhD in Computer Science in 1969, University of Utah College of Engineering
1972: invention of Object-Oriented Programming, and the programming language Smalltalk at Xerox Parc, Palo Alto, California.
Bjarne Stroustrup, 1950-¶
Masters in Mathematics in Aarhus University, Denmark, 1975
PhD in Computer Science from University of Cambridge, 1979
1979 Invented the C++ programming language
Guy Steele, 1954-¶
PhD in Computer Science from MIT, 1980
1995 Co-created Java, the most used programming language (due to one of its runtime environment: Android).
Functional Programming¶
John McCarthy, 1927 - 2011¶
PhD in Mathematics in 1951, Princeton University
1955: Coined the term artificial intelligence
Knowns as one of the founding fathers of artificial intelligence.
1958: Invented the Lisp programming language, probably the most influential programming language ever created.
tree data structures (found in Python, Go, Ruby, Javascript, …)
automatic garbage collection (in Python, Go, Java, Javascript, Ruby, …)
dynamic typing (in Python, Javascript)
REPL: read-eval-print loop (in Python, SHELL, Scala, Ruby, …)
Gerald Jay Sussman, 1948-, and Guy L Steele¶
Sussman received his PhD from MIT in 1973, and has been a professor in Electrical Engineering at MIT ever since then. His research has always been in A.I. and its applications in engineering.
1975 invented Scheme with his student Guy Steele.
Scheme is still actively used (latest release in 2013). It is considered one of the most efficient Lisp dialects available.
Simon Peyton Jones, 1958-¶
Graduated from Cambridge in 1980
Since 1998, Peyton Jones has been with Microsoft Research in Cambridge, England.
In 1990, co-invented Haskell the pure functional programming language with one of the most powerful type system.
Still a lead developer of the most popular Haskell compiler, the Glasgow Haskell Compiler (GHC).