PU1

A world view through the computational lens : 

A world view through the computational lens Avi Wigderson Institute for Advanced Study 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

Slide 2: 

Theory of computing Math Computer Science Biology, Physics Economics,…

Intelligence: Man versus Termite : 

Intelligence: Man versus Termite Patterns vs. brain size SURVEY Are termites intelligent? Humans (~1011 neurons) Termites (105 neurons) 2 3 5 7 11 13 17 19 23 2 3 5 7 11 13 17 19 23 Voyager face plate

Slide 4: 

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 : 

Computation is everywhere- Long list of natural phenomena and intellectual challenges- All have an essential computational component

Slide 6: 

What is computation ? before after

Slide 7: 

What is computation ? before after ?

Slide 8: 

What is being computed? Function. What are possible inputs? Representation? How to describe a computational process? What is being manipulated? Cells/digits 9876543 + 555555 input function output

Slide 9: 

1 month 3 months 2 pm 4 pm What laws govern these processes? Good theories are predictive: Nature computes the outcome – can we?

Slide 10: 

4/11/03 4/30/03 +15h +24h Will it spread, or die out?

Slide 11: 

Can we automate Andrew Wiles? Is there a program to solve all equations? to prove all provable theorems? X2 + Y2 = Z2 Xn + Yn = Zn n>2 X=3 Y=4 Z=5 Theorem: no solution! Proof: Does not fit on this slide (200 pages)

Slide 12: 

“my aunt Esther” sadness 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.

Slide 13: 

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 Start: 9th av. New York, NY public lecture princeton 07 End: Nassau st, Princeton, NJ 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 do they do it? Is there a better way?

Slide 14: 

How to describe computation? Algorithms in Mathematics

Slide 15: 

Function: input  output ALGORITHM (intuitive def): Step-by-step, simple mechanical procedure, to compute a function on every possible input addition algorithm 12345 + 6789 19134 input output Algorithms in Mathematics 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]

Slide 16: 

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: e.g. GCD(12,15)=3 Math proof & algorithms always walked hand in hand Father of Geometry function GCD (a, b) while a ≠ b if a > b then a := a – b else b := b - a return a

Slide 17: 

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 Algebra

Slide 18: 

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 Father of Computing

Slide 19: 

9 8 7 6 5 4 3 2 1 1 1 1 3 1 4 1 9 “Long addition” algorithm Scan column. If empty, stop. Add digits. Write answer, retain carry. Move one column left, write carry. Go to 1

Slide 20: 

9 8 7 6 5 4 3 2 1 1 1 1 3 1 4 1 9 ALGORITHM: Step-by-step, local, simple, mechanical procedure, which evolves an environment 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

Slide 21: 

Turing machine Demo

Slide 22: 

“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

Slide 23: 

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

Slide 24: 

Universality Universal Turing machine U: input: (M,x) output: M(x) Computers can be programmed! U: hardware M: software …Computer revolution… Practice after Theory

Slide 25: 

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!

Slide 26: 

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

Slide 27: 

An incomputable problem Does a given computer program P halt on all inputs? Typical program 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 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)

Slide 28: 

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?

Slide 29: 

Algorithms In Nature

“Life, the Universe, and Everything” : 

“Life, the Universe, and Everything” Computation: evolution of an environment via repeated application of simple, local rules (Almost) all Physics and Biology theories satisfy! Weather - Proteins in a cell - magnetization Ant hills - Fish schools - fission Brain - Populations - burning fire Epidemics – Regeneration - growth applied simultaneously everywhere

Nature’s algorithms:von Neumann’s Cellular Automata : 

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 : 

Evolution: Majority rule Time 0 1 2 3 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?

Artificial Life? Intelligence? : 

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 : 

Algorithms can explain nature Synchrony & self stabilization Fireflies coordinating their flashing Heart muscles contracting in rhythm Neurons firing in unison …

Synchrony & self stabilization : 

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 : 

Beauty from algorithms

Summary : 

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 : 

Plan for the coming lectures

Slide 39: 

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

Computation is everywhere : 

Computation is everywhere US Shortest Route Unsolvable Solvable Game Strategies Multiplication Addition Pattern Matching Shortest Route Theorem Proving Map Coloring NP-complete SAT Integer Factoring Graph Isomorphism P FFT NP

Slide 41: 

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?