CompSci 100E36.1On the Limits of Computingÿ Reasons for Failure1. Runs too longo Real time requirementso Predicting yesterday's weather2. 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 obviousquestionsÿ 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:ateachadded step, work multiplies rather than addsÿ Exponential = Intractableÿ Traveling Salesperson Exampleþ Visit N Cities in Optimal Orderþ Optimize for minimum:o Timeo Distanceo Costÿ N factorial (N!) Possibilitiesÿ N! is (very) roughly NNþ 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 statementin 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 cancheck 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 loopand goes on foreverþ If halt program decides it doesn't halt, it quitsimmediatelyÿ Therefore halt cannot exist!ÿ Whole classes of programs on program behavior arenon-computableþ Equivalenceþ Many other programs that deal with the behavior of aprogramCompSci 100E36.18Living with Noncomputabilityÿ What Does It All Mean?þ Not necessarily a very tough constraint unless you get “toogreedy”.þ Programs can't do everything.o Beware of people who say they
View Full Document
Unlocking...