- Learn what general-purpose computation is
- Learn the who's-who in the early study of computation
- Learn about the Church-Turing Thesis
Why do I have to build data structures and what are they for? Data structures are specific examples of mechanical, automated problem solving.
Computers in 1880 were men and more often women who would work out formulas with pen and paper for an hourly rate. Calculations were needed for phsyics and chemistry research, calculus, other mathematics, and finances. This lead to an academic discipline that involved philosophy about the nature of mathematics and what kinds of knowledge could be formally proven.
Alonzo Church, Alan Turning, Stephen Kleene, Kurt Godel, David Hilbert, and others worked to formalize these ideas into mathematical proofs leading, eventually, to the Turing Machine and the proofs that accompanied it.
It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.
Alan Turing (1939) in The Undecidable, p. 160
Something is numerically computable by a human if-and-only-if it is computable by a Turing machine, and that all forms of iterative deterministic computation are equivalent.
Have you ever wondered where the Lambda in Lambda School came from? Wonder no more. It's from Lambda Calculus, or λ-calculus.
λ-calculus is a formal mathematical system for modeling computation. It provably is able to support all the same computational abilities that a Turing Machine does.
One of the most common places the λ-calculus makes an appearance is in functional programming languages such as LISP.
Functional Programming is what is called a programming paradigm. Object-Oriented Programming is another (e.g. JavaScript, C++). Procedural is another (e.g. C). (Although truly most languages are mixed-paradigm.) It is usually more difficult to learn a new programming paradigm than it is to learn another language of the same paradigm.
Alan Turing came up with the Turing Machine model of computation. At the same time, Alonzo Church came up with the Lambda Calculus model. Church and Turing proved these two models to be equivalent with the Church-Turing Thesis.
The pursuit of ancient philosophy from Aristotle and Stoic philosophers near 300 BCE:
If the first, then the second; the first, therefore the second.
If the first, then the second; not the second, therefore not the second.
Not the first and the second both; the first, therefor not the second.
The first or the second but not both; the first, therefor not the second.
The first or the second one or the other; not the second, therefore the first.
Not a direct antecedent of Computer Science, Calculus instead is part of the train of reasoning that informs all of the modern world: Logic and formal analysis can describe the behavior of things.
George Boole and Augustus DeMorgan in the mid 1800s expanded on ancient propositional calculus into a formal algebra:
A ∨ B (A or B)
A ∧ B (A and B)
¬A (not A)
A ⇒ B (A implies B)
A ⇔ B (A if and only if B)
Charles Babbage (1791-1871)
Charles Babbage first proposed that these formal rules could be automated. He built part of the Difference Engine and proposed the design of the Analytical Engine. His work became the foundation of formal automata theory.
Ada Lovelace (1815-1852)
The first computer programmer, Ada Lovelace studied under Charles Babbage and created the first languages to automate the unbuilt Analytical Engine.
Principia Mathematica (Not the one by Newton!) was written by Alfred North Whitehead and Bertrand Russell. It was an attempt to describe all of mathematics from a set of starting axioms. This was the culminative attempt of formal logicians to capture "reasoning ability" into a formal method, and profoundly influenced the development of computer systems.
Halting Problem This is of special importance in Computer Science!
One of the first decision problems and the foundation of Computer Science. The Turing Machine was invented in order to provide a solution for this problem - that it is undecidable.
The question is: Can a program be written f that will for every other program
g say whether or not g will finish? Turing proves using complicated
mathematics, and by inventing a Turing Machine in order to support his proof,
that this machine f cannot be invented.
The takeaway from this proof and observation is that it is not possible to build a computer program that can solve any problem - some problems are undeciable, that is, unsolveable.
Turing Machines These are of special importance in Computer Science!
Visual example of a Turing Machine as formula
Gödel's Incompleteness Theorem
-
Where do you see boolean algebra used in JavaScript?
-
What are some examples of logical symbols in JavaScript?
-
The Analytical Engine was never constructed. Why not?