CompSci 100E36.1On the Limits of Computingÿ Reasons for Failure1. Runs too longo Real time requirements o Predicting yesterday's weather 2. Non-computable !3. Don't know the algorithm ÿ Complexity, N Time Space ÿ Tractable and IntractableCompSci 100E36.2On the Limits of Computingÿ Intractable Algorithms Computer "crawls" or seems to come to halt for large N Large problems essentially unsolved May never be able to compute answer for some obvious questions ÿ Chess Here N is number of moves looking ahead We have an Algorithm! o Layers of look-ahead: If I do this, then he does this, .... o Problem Solved (?!) Can Represent Possibilities by Tree Assume 10 Possibilities Each Move t = A * 10^N ÿ Exponential ! ! !CompSci 100E36.3Exponential Algorithmsÿ Recognizing Exponential Growth Things get BIG very rapidly Numbers seem to EXPLODE KEY: at each added step, work multiplies rather than addsÿ Exponential = Intractable ÿ Traveling Salesperson Example Visit N Cities in Optimal Order Optimize for minimum: o Time o Distance o Cost ÿ N factorial (N!) Possibilities ÿ N! is (very) roughly N N Sterling’s approximation: N! = sqrt(2*Pi*N)*(N/e)Nÿ Typical of some very practical problemsCompSci 100E36.4Traveling Salesperson Examplesÿ 3 cities 2! = 2 possible routes (1 of interest) abc acbÿ 4 cities 3! = 6 possible routes (3 of interest) abcd abdc acbd acdb adbc adcbÿ (Only half usually of interest because just reverse ofanother path)CompSci 100E36.5Traveling Salesperson Examples5 cities 4! = 24 possible routes abcde abced abdce abdec abecd abedc acbde acbed acdbe acdeb acebd acedb(12 of interest) adbce adbec adcbe adceb adebc adecb aebcd aebdc aecbd aecdb aedbc aedcbCompSci 100E36.6Towers of HanoiNt t = 0.00549 * 2N5 .17 sec (for a very old PC)10 5.62 sec15 3.00 min20 1.6 hour25 2.13 day30 68.23 day35 5.98 year What would a faster computer40 191.3 year do for these numbers?45 6120 year50 196 K year55 6.27 M year60 201 M year65 6.42 G year70 205 G yearCompSci 100E36.7Intractable Algorithmsÿ Other Gamesÿ More hardware not the answer!ÿ Predicting Yesterday's Weather ÿ Actual Examples for Time ComplexityCompSci 100E36.8Existence of Noncomputable Functionsÿ Approach Matching up Programs and Functions E.g., assume 3 functions, only 2 programs Without details, conclude one function has no program ÿ Have: Uncountable Infinity of Functions Mappingint to int How can we show that is true? Functions can be seen as columns in tables Put all functions into a huge (infinite!) table Show that even that cannot hold them all Can you identify the functions in the following table?CompSci 100E36.9Table ofAllInteger to Integer Functions1126008214..2447018417..39680086210..4168911816313..525101010810516..636121111836819..7491412108141322..8641613118642125..9811814108183428..........................CompSci 100E36.10AFunctionNOTin this (inclusive?) Table1+1 126008214..2 4+1 47018417..396+1 80086210..416 8 9+1 11816313..5251010 1+1 0810516..6361211 1 1+1 836819..7491412 1 0 8+114 13 22 . .864161311864+121 25 . .98118141081834+128..1010020151181005531+1 ..........................CompSci 100E36.11Existance of Noncomputable Functionsÿ All Programs Can be Ordered (thus Countable) By size, shortest program first Just use alphabetical order ÿ Try to Draw Lines Between Functions and Programs Could draw lines from every program to every function But, have proved functions uncountable... Thus, There Must be Functions With NO Programs! ÿ Hard to come up with function that computer can't produce Possible example: true random generator(No algorithm can produce truly random number sequence) Use Table Program must be of finite size; Requires infinite tableCompSci 100E36.12Noncomputable Programsÿ Programs that Read Programs What programs have we used that read in programs? Express programs as a single string (formatting messed up) Therefore, could write program to see if there is an if statement in the program: answers YES or NO How about, Does program halt? Lack of while (and functions) guarantees a halt Not very sophisticated Not Halting for All Possible Inputs is usually considered a Bug ÿ Solving the Halting Problem Write specific code to check out more complicated cases Gets more and more involved...CompSci 100E36.13The Halting Problem: Does it Halt?ÿ Consider Following Program: Does it halt for all input?// input an integer value for kwhile (k > 1){if ((k/2)*2==k) //iskeven?k=k/2;elsek=3*k+1;}ÿ Try It! e.g. 17: 52 26 13, 40 20 10 5, 16 8 4 2 1 For a long time, no one knew whether this quit for all inputs.CompSci 100E36.14Proving Noncomputabilityÿ Mathematicians have proven that no one, finite program can check this property for all possible programs ÿ Examples of non-computable problems Equivalence: Define by same input > same output Use variation of above program; not sure it ends Cannot generally prove equivalence ÿ Use Proof by Contradiction (Indirect Proof) ÿ Proving non-computability Sketch of proofCompSci 100E36.15Noncomputability Proofÿ Assume Existence of Function halt:String halt(String p, String x); Inputs: p = program, x = input data Returns: "Halts"or "Does not halt"ÿ Can now write: String selfhalt(String p); Inputs: p = program Returns: "Halts on self"or "Does not halt on self" Uses: halt(p, p); i.e.: asking if halts when program p uses itself as dataCompSci 100E36.16Noncomputability Proof.2ÿ Now write function contrary:void contrary();{TextField program = new TextField(1000);String p, answer;p = program.getText();answer = selfhalt(p);if (answer.equals("Halts on self")){while (true) // infinite loopanswer = "x";}elsereturn; // i.e., halts}ÿ "Feed it" this program.CompSci 100E36.17Noncomputability Proof.3ÿ Paradox! If halt program decides it halts, it goes into infinite loop and goes on forever If halt program decides it doesn't halt, it quits immediatelyÿ Therefore halt cannot exist!ÿ Whole classes of programs on program behavior are non-computable Equivalence Many other programs that deal with the behavior of a programCompSci 100E36.18Living with Noncomputabilityÿ What Does It All Mean? Not necessarily a very tough constraint unless you get “too greedy”. Programs can't do
View Full Document
Unlocking...