01. What is a Computer?
Computers
15/03/2023
Definition
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically.
Computer is a machine designed to solve problems automatically
Little story
Little story
Antikythera mechanism (87 BC)
The oldest known example of an analogue computer used to predict astronomical positions and eclipses decades in advance.
Little story
Jacquard machine (1804)
Simplifies the process of manufacturing complex textiles he machine. Was controlled by a chain of punched cards;
Little story
The differential engine (1820)
A mechanical calculator designed to tabulate polynomial functions. Was first created by Charles Babbage and is considered the first moder computer.
Analog and Digital
Analog computers
Is a type of computer that uses the continuous
variation aspect (analog signals) to model the problem
being solved.
Example of analog computer
Here is tide predictor machine that, using a sequence of pulley, can
predict (compute) tides. This is conceptually similar to
the Antikythera mechanism.
Digital computers
Is a type of computer that uses the discrete form
(discrete inputs) to model the problem being solved.
Example of Digital computer
The Lehmer sieve in 1926 was made using chains of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switches, and when all the switches were closed simultaneously a solution had been found
The computer science
Hilbert Problems(1900)
Among the 23 problems stated by Hilbert we summarize them in three questions and those were not just questions in mathematics; they were questions about mathematics itself
Completeness of Math
- Is mathematics complete? That is, can every mathematical statement be proved or disproved from a given finite set of axioms?
- Is mathematics consistent? In other words, can only the true statements be proved?
- Is every statement in mathematics decidable? There is a definite procedure that can be applied to every statement that will tell us in finite time if the statement is true or false?
Kurt Gödel
Kurt Gödel in 1930 answered to the first two stating shortly that if the answer to question 2 above is “yes” (i.e., mathematics is consistent), then the answer to question 1 (is mathematics complete?) has to be “no.”
Entscheidungsproblem
The last question is known by its German name as the Entscheidungsproblem (“decision problem”), and goes back to the seventeenth-century mathematician Gottfried Leibniz. Leibniz actually built his own calculating machine, and believed that humans could eventually build a machine that could determine the truth or falsity of any mathematical statement.
Alan Turing
The decision problem was answered by Alan Turing in 1935 and the answer was no, (the halting problem) but doing this he create the computer concept as we know it today.
Alan turing did this when he was twenty-three-year-old as graduated student under the logician Max Newman
Leibniz Legacy
Following the intuition of Leibniz of more than two centuries
earlier, Turing formulated his definition by thinking about a powerful
calculating machine that could not only perform arithmetic but also
could manipulate symbols in order to prove mathematical
statements.
Thought Machine
By thinking about how humans might calculate, he constructed a mental design of such a machine
The Turing machine turned out to be a blueprint for the invention of the electronic programmable computer.
Turing Machine
is composed by a tape where an head can
scroll in any direction and can read/write symbols on it. The
head can use a finite control made up with
rules eg: if tape cell read is (x) then
move to next tape cell and write (y) …
Limits!
- This thought machine has set the definition of definite procedure, fixing an ill-defined notion,
- Has blueprinted and paved the way to modern computers
- Has given bird to the computer science, exploiting the
halting problem and demonstrating that
there are limits to what can be computed.
von Neumann
The von Neumann architecture consists of a
random access memory (RAM) that stores both program
instructions and data, and a central processing unit (CPU)
that fetches instructions and data from memory and executes the
instructions.
Cellular Automaton
A forward step
von Newman working in Los Alamos with Stanislaw Ulam start thinking about a different architecture of computer mainly to solve fluid motions problems
Definition
A cellular automaton consists of a regular grid of cells, each in one
of a finite number of states, such as on and off. An initial state
(time t = 0) is selected by assigning a state for each
cell. A new generation is created (t = t+1), according to
some rules that determines the new
state of each cell in terms of the current state of the
cell and the states of the cells in its neighborhood on grid.
cellular grids
Conway’s Game of Life
- Any live cell with two or three live neighbours survives.
- Any dead cell with three live neighbours becomes a live cell.
- All other live cells die in the next generation. Similarly, all other dead cells stay dead.
Guns and Glider
Wolfram Automaton
Steven Wolfram simplified the concept of cellular automata using just 8 bits to create 256 possibile rules, and discover this:
Rule 110
Automaton 256 rules
Universal computer
A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute (another term for this is Turing-complete). A cellular automaton in which such a system exists is called universal. A universal computer may be either infinite or finite, but when combined with a universal constructor, it is assumed to be finite.
Chaos and Order
Rule 110 was proved to be an Universal
Computer but Rule 30 seem to be hitting the edge
from Chaos and Order in the field of complexity, leading to an idea
of
Complexity
New Kind Of Science
- The proper way to think about processes in nature is that they are computing.
- Since even very simple rules can support universal computation, the ability to support universal computation is very common in nature.
New Kind Of Science
- Universal computation is an upper limit on the complexity of computations in nature. That is, no natural system or process can produce behavior that is “noncomputable.”
- The computations done by different processes in nature are almost always equivalent in sophistication.
Conclusion
