Transcript The Power of randomness - IAS - Institute for Advanced Study

A world view through the
computational lens
I
Algorithm: the common language of
nature, humans and computer
II Time, space and the cosmology
of computational problems
III Secrets and lies, knowledge and trust
Avi Wigderson
Institute for Advanced Study
Math
Theory
of
computing
Computer
Science
Biology, Physics
Economics,…
Intelligence: Man versus Termite
Patterns vs. brain size
SURVEY
Are termites intelligent?
Voyager face plate
2 3 5 7 11 13 17 19 23
Humans (~1011 neurons)
2
3
5
7
11
13
17
19
23
Termites (105 neurons)
Lecture I - plan
--------
Computation is everywhere
Algorithms in Mathematics
The Turing Machine
Limits on CS and Math knowledge
Algorithms in Nature
von Neumann cellular automata
Limits on scientific knowledge
Computation
is everywhere
- Long list of natural phenomena
and intellectual challenges
- All have an essential computational
component
What is computation ?
before
Hair implant
process
after
What is computation ?
12345
+ 6789
before
Hair loss
process
after
?
input
Long addition
process
19134
output
before
Hair loss
after
12345
+ 6789
9876543
+ 555555
Long addition
19134
input
function
output
What is being computed? Function.
What are possible inputs? Representation?
How to describe a computational process?
What is being manipulated? Cells/digits
2 pm
1 month
Fetal
development
3 months
Weather
evolution
4 pm
What laws govern these processes?
Good theories are predictive:
Nature computes the outcome – can we?
+15h
4/11/03
SARS infection
(in the world)
SARS infection
(in the cell)
+24h
4/30/03
Will it spread, or die out?
X2 + Y2 = Z2
Solving integer
equations
X=3 Y=4 Z=5
Xn + Yn = Zn n>2
Proving
theorems
Theorem: no solution!
Proof: Does not fit on
this slide (200 pages)
Can we automate Andrew Wiles?
Is there a program to solve all equations?
to prove all provable theorems?
Indonesian 737-400 feared lost
with 102 aboard.
Indonesia's transportation minister
said Tuesday that rescuers had not
found the wreckage of a missing
passenger jetliner, despite earlier
statements from aviation and police
officials that it had been located.
Face
recognition
Emotional
reactions
“my aunt Esther”
sadness
How do they do it?
Is there a better way?
public lecture princeton 07
Web
search
Start: 9th av. New York, NY
End: Nassau st, Princeton, NJ
Public Lectures at Princeton » 2006-2007 Lectures
Lectures are free and open to the public. Lectures are
in McCosh 50 and begin at 8:00 p.m. unless ...
lectures.princeton.edu/?cat Cached - Similar pages
Shortest
route
1. Start out going SOUTHWEST on 9TH AVE toward W 57TH ST. 1.0 miles
2. Take the LINCOLN TUN ramp toward NEW JERSEY.
0.1 miles
3. Merge onto I-495 W (Crossing into NEW JERSEY).
0.9 miles
4. I-495 W becomes NJ-495 W.
3.2 miles
5. Merge onto I-95 S / NEW JERSEY TURNPIKE S via the exit
on the LEFT toward I-280 / NEWARK / I-78 (Portions toll).
6.3 miles
6. …
How to describe computation?
Algorithms in
Mathematics
Algorithms in Mathematics
Function: input  output
ALGORITHM (intuitive def):
Step-by-step, simple
mechanical procedure,
to compute a function
on every possible input
12345
+ 6789
input
addition
algorithm
19134
output
History & Heroes (millennia scale)
-2,300 years: Euclid
[proofs and algorithms]
-1,100 years: al-Khwārizmī [namesake of algorithms]
-70 years: Turing
[defined algorithms]
Father of Geometry
Euclid ~330-275 BC
Employment: Library of Alexandria
Selected achievements:
The Elements: 13 volumes on
Geometry and Number Theory
Most popular math book for centuries
Math proofs: step-by-step deduction from axioms
The GCD algorithm:
function GCD (a, b)
while a ≠ b
e.g. GCD(12,15)=3
if a > b
then a := a – b
Math proof & algorithms always
else b := b - a
return a
walked hand in hand
Father of Algebra
al-Khwārizmī ( latin algorithmi )
Employment: House of Wisdom,
Baghdad, 813-846 AD
Selected Publications:
Geography: On the appearance of the earth
Astronomy: Astronomical tables
Algebra: Calculation by completion and balancing
Arithmetic: On the Hindu art of reckoning
- Describes the positional number system (digits)
- Gives algorithms for arithmetic operations,
and for solving linear and quadratic equations
Father of Computing
Alan Mathison Turing 1912-1954
Selected achievements:
1936: “On computable numbers, with
an application to the entscheindungsproblem”
Formal definition of an algorithm
Foundations of Computer Science
1939-1945: Blechley Park, breaking Enigma
1945-1949: building ACE, MARK-I
Early electronic general purpose computers
1950: “Computing machinery and intelligence”
Foundations of Artificial Intelligence
“Long addition” algorithm
1
1
1.
2.
3.
4.
1
1
1
2
3
4
5
6
7
8
9
1
3
9
4
Scan column. If empty, stop.
Add digits. Write answer, retain carry.
Move one column left, write carry.
Go to 1
ALGORITHM:
Step-by-step, local,
simple, mechanical
procedure, which
evolves an environment
1
1
1
1
1
2
3
4
5
6
7
8
9
1
3
9
4
Environment: infinitely many cells, regular
Cell: can hold one symbol from a finite alphabet
Head
local moves, read/write symbol,
has a state which “remember” a few symbols
ALGORITHM: finite table of instructions
Can handle infinite number of different inputs
Turing machine
Demo
“On computable numbers,
with an application to the
entscheindungsproblem” 1936
Turing’s insights
-
What is computation [& what is computed]
Duality of program and input
Universality [& the computer revolution]
The power of computation
The limits of computation
What is computation
Formal definition of an algorithm:
A Turing machine which halts in finite time
on every possible (finite) input.
Machine M on input x computes M(x)
Duality
Input:
a finite sequence of symbols x
Program: a finite sequence of symbols M
Program and input are interchangeable!
A program can be input to another program
Universality
Universal Turing machine U:
input: (M,x)
output: M(x)
Computers can be programmed!
U: hardware
M: software
M1: Spell check a file
M2: Calculate salaries
M3: Run computer game
2006
1946
M4: Play music
M5: Show movie
M6: Surf the Web
…Computer revolution… Practice after Theory
The power of computation
Church-Turing Thesis: Every function
computable by any reasonable device,
is computable by a Turing machine
Thesis stood unchallenged for 70 years!
Corollary: Java, C++, CRAY,.. Can be
Corollary: Every natural process can be
simulated by a Turing machine.
THINK ABOUT IT!
The limits of computation
Are there
limits ??
Turing ‘36: no algorithm can solve these
- Given a program, does it have a “bug”?
- Given a math statement, is it provable?
’36-’06: … and many other natural ones
An incomputable problem
Does a given computer program P
halt on all inputs?
Typical
program
Input: x (integer)
Program P0
(1) if x=1 halt
(2) if x is even, set x  x/2 and go to (1)
(3) if x is odd, set x  3x+1 and go to (1)
X=8: 8, 4, 2, 1
X=6: 6, 3, 10, 5, 16, 8, 4, 2, 1
- So far, Math cannot answer this for P0
- No algorithm can answer this for all P
Turing’s proof: uses duality & universality
The limits of computation
Many natural incomputable functions!!
- Is a given computer program bug-free?
- Is a math statement provable?
- Is a given equation solvable?
Absolute limits on what can be known in
Mathematics and Computer Science!
What about the Natural Sciences?
Algorithms
In
Nature
“Life, the Universe, and Everything”
Computation: evolution of an environment via
repeated application of simple, local rules
applied simultaneously everywhere
(Almost) all Physics and Biology
- Weather - Proteins in a cell
- Ant hills - Fish schools
- Brain
- Populations
- Epidemics – Regeneration
theories satisfy!
- magnetization
- fission
- burning fire
- growth
Nature’s algorithms:
von Neumann’s Cellular Automata
-A
environment of cells
e.g. a (large) grid
-
A neighborhood structure
e.g cells “touching” you
-
Every cell has finite state
e.g “yellow” or “green”
[representing biological,
chemical, physical,… info.]
-
Update rule e.g. Majority
- Initial configuration
TM: sequential update
CA: parallel update
Evolution: Majority rule
Majority: assume color
of majority of neighbors
Will the Green population
ever die out?
What happens if we
replace the Majority
by another local rule?
Time 0
3
12
Artificial Life? Intelligence?
Some rules simulate a universal Turing
machine (eg Conway’s “Game of Life”).
Conclusions:
- Incomputable to predict evolution in CA
- CA can self reproducing (is it alive?)
- CA can list prime numbers (intelligent?)
Termites’ brain can implement any CA rule
They can list primes, and generate any
structure computers & humans can !
Algorithms can explain nature
Synchrony & self stabilization
• Fireflies coordinating their flashing
• Heart muscles contracting in rhythm
• Neurons firing in unison
• …
Synchrony & self stabilization
Programming challenge: design termite to:
• Put any number of termites in a row.
• Kick any one of them (gently)
• After finite time steps, they march
Beauty from algorithms
Summary
- Computation is everywhere
- Turing machine: capture all computation
- Algorithmic thinking and modeling reveals
new aspects of: natural phenomena,
mathematical structures, and our limits
to understanding in math & science
Plan for the
coming lectures
I
Algorithm: the common language of
nature, humans and computer
II Time, space and the cosmology
of computational problems
III Secrets and lies, knowledge and trust
- Hard and easy problems.
- The importance of efficient algorithms
- The P vs. NP problem, and why is it
so important to science & mathematics
- The ubiquity of NP-complete problems
Solvable
Unsolvable
Game
Strategies
Graph
Isomorphism
Computation is
everywhere
NP-complete
Integer
Factoring
SAT
Theorem
Proving
Shortest
Route
NP
Shortest
Route
P
Map
Coloring
Pattern
Matching
Multiplication
Addition
FFT
US
I
Algorithm: the common language of
nature, humans and computer
II Time, space and the cosmology
of computational problems
III Secrets and lies, knowledge and trust
- The amazing utility of hard problems
- The assumptions and magic behind security
of the Internet & E-commerce
- How to play Poker, but
without the cards?