Charles Babbage designed a mechanical programmable computer in the 1830's, well ahead of his time. He is considered one of the first computer/information scientists.

The difference engine was never implemented in his lifetime. The technology was not sufficiently advanced.

Mechanical switches tend to be slow and prone to mechanical failure.

150 years later, a replica was built and it did work.

Ada Lovelace, assistant to Charles Babbage, is considered the first programmer, although the programs she wrote would never be executed in her lifetime.

The programming language Ada is named after Ada Lovelace.

Alan Turning (1912-1954) published his work on the limits of computation and what would later be called the Turning machine in 1936. Turing needed to invent such a theoretical computer in order to prove some computability (and non-computable) properties.


Alan Turing helped break the German Enigma machine encryption during World War II (shortening the war by at least a year) and later defined a test to determine if a computer is intelligent.

But every computable computation (or, math terms, every recursively enumerable function) could be computed on a Turing Machine, a simplified model of computation that made use of a tape, a read-write head, and a control mechanism.

A Turing machine is an operational computer.

A Turing complete computer programming language is a language that can compute every computable function.

The most famous such undecidable problem is that Halting Problem. That is, write a computer program that, given any other computer program (and its data), decides whether that computer program (and its data) ever halts. It cannot be done.

Alonzo Church (1903-1995) was an American logician who invented the lambda calculus.

The Church-Turing hypothesis forms the basis of the limits of computation.

• Turing used an operational definition of a computing machine that become the basis of modern electronic digital computers.
• Church used functions and mathematics for a language that became Lisp and formed the foundation of modern functional programming languages.

Both systems can compute the same functions (and have the same limitations).

The lambda calculus is very simple.

An expression E is one of the following.

• A constant C
• A variable X
• An application of an expression to an expression as ( E . E )
• A function as lambda x . E (where x is the argument and E the body of the function)

The purpose of a simple language like lambda calculus is that properties of programming languages need only be proved for a few constructs.

Such a proof is called a structural induction proof.

Code can be data and data can be code. Von Neumann first recognized this principle.

Today, the conventional and traditional computer design is called a Von Neumann machine.

5 questions omitted (login required)