Princeton COS 116 - What computers just cannot do

Unformatted text preview:

What computers just cannot do. COS 116, Spring 2012 Adam Finkelstein“Prof, what’s with all the negative thinking?!?”  An obvious motivation: Understand the limits of technology “What computers can’t do.”The power of negative thinking….In Science….  Impossibility of trisecting angle with ruler and compass (Galois) Often, impossibility result deep insight Examples  Nothing travels faster than light Group Theory and much of modern math Relativity and modern physicsIn Mathematics….. “Can mathematicians be replaced by machines?” Axioms – Set of statements Derivation rules – finite set of rules for deriving new statements from axioms Theorems – Statements that can be derived from axioms in a finite number of steps Mathematician – Person who tries to determine whether or not a statement is a theorem. [Hilbert, 1900] Math is axiomatic“Given starting configuration for the game of life, determine whether or not cell (100,100) is ever occupied by a critter.” John Conway Understanding complex systems (or even simple systems)…. Can a simple set of mathematical equations “solve” problems like:In computer science…… Cryptography CAPTCHAMore Computer Science… Automated Software Checking? Windows Vista: 50-million line program Can computers check whether or not it will ever crash?Discussion Time What is a computation? (need to know this to know what can/cannot be computed) Next: How did Turing set about formalizing this age-old notion and what were the features of his model?What is a computation? Basic Elements  Scratch Pad  Step-by-step description of what to do (“program”); should be finite!  At each step:  Can only scan a fixed number of symbols  Can only write a fixed number of symbols (see reading by Davis)Turing’s model  1 dimensional unlimited scratchpad (“infinite tape”)  Only symbols are 0 or 1 (tape has a finite number of 1s)  Can only scan/write one symbol per step  Program looks like 1. PRINT 0 2. GO LEFT 3. GO TO STEP 1 IF 1 SCANNED 4. PRINT 1 5. GO RIGHT 6. GO TO STEP 5 IF 1 SCANNED 7. PRINT 1 8. GO RIGHT 9. GO TO STEP 1 IF 1 SCANNED 10. STOP The Doubling ProgramExample: What does this program do? 1. PRINT 0 2. GO RIGHT 3. GO TO STEP 1 if 1 SCANNED 4. GO TO STEP 2 if 0 SCANNEDLet’s try another… http://ironphoenix.org/tril/tm/Discussion Time Can this computational model do every computation that pseudocode can? How do we implement arithmetic instructions, arrays, loops?Surprising facts about this simple model  It can do everything that pseudocode can do Hence it can “simulate” any other physical system, and in particular simulate any other physically realizable “computer.” [CHURCH-TURING THESIS”] THIS MODEL CAPTURES THE NOTION OF “COMPUTATION” ----TURINGRecall: Numbers and letters can be written in binary. A program can also be represented by a string of bits!“Code” for a program Many conventions possible (e.g., ASCII) Davis’ convention: P Code (P) = Binary RepresentationPrograms and Data Usual viewpoint - A False Dichotomy! Program Data But can have - Program Code of ProgramUniversal Program U  U “simulates” what P would do on that data Data U Program P (Sometimes also known as “interpreter”)D V Automated Bug Checking Revisited Halting Problem Let P = program such that code(P) = V. Does P halt on data D? Trivial Idea: Simulate P using universal program U. If P halts, will eventually detect. Problem: But if P never halts, neither does the simulation. IDEAS???Next Week: Halting Problem is unsolvable by another program Homework for next week will be posted this afternoon. Includes: Write a Turing-Post program that prints the bit sequence 101 infinitely often, as well as its binary code Thurs: Digital audio (guest: Prof. Fiebrink) Read this proof in the Davis article, and try to understand. Ponder the meaning of “Proof by contradiction.” How convincing is such a proof? “When something’s not right, it’s wrong…” -Bob


View Full Document

Princeton COS 116 - What computers just cannot do

Documents in this Course
Lecture 5

Lecture 5

15 pages

lecture 7

lecture 7

22 pages

Lecture

Lecture

32 pages

Lecture

Lecture

16 pages

Midterm

Midterm

2 pages

Lecture

Lecture

23 pages

Lecture

Lecture

21 pages

Lecture

Lecture

24 pages

Lecture

Lecture

22 pages

Lecture

Lecture

28 pages

Lecture

Lecture

21 pages

Lecture

Lecture

50 pages

Lecture

Lecture

19 pages

Lecture

Lecture

28 pages

Lecture

Lecture

32 pages

Lecture

Lecture

23 pages

Lecture

Lecture

21 pages

Lecture

Lecture

19 pages

Lecture

Lecture

22 pages

Lecture

Lecture

21 pages

Logic

Logic

20 pages

Lab 7

Lab 7

9 pages

Lecture

Lecture

25 pages

Lecture 2

Lecture 2

25 pages

lecture 8

lecture 8

19 pages

Midterm

Midterm

5 pages

Lecture

Lecture

26 pages

Lecture

Lecture

29 pages

Lecture

Lecture

40 pages

Lecture 3

Lecture 3

37 pages

lecture 3

lecture 3

23 pages

lecture 3

lecture 3

20 pages

Lecture

Lecture

21 pages

Lecture

Lecture

24 pages

Lecture

Lecture

19 pages

Load more
Download What computers just cannot do
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view What computers just cannot do and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view What computers just cannot do 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?