On the Limits of ComputingSlide 2Exponential AlgorithmsTraveling Salesperson ExamplesSlide 5Towers of HanoiIntractable AlgorithmsExistence of Noncomputable FunctionsTable of All Integer to Integer FunctionsA Function NOT in this (inclusive?) TableExistance of Noncomputable FunctionsNoncomputable ProgramsThe Halting Problem: Does it Halt?Proving NoncomputabilityNoncomputability ProofNoncomputability Proof.2Noncomputability Proof.3Living with NoncomputabilityCompSci 100E34.1On the Limits of ComputingReasons for Failure 1. Runs too long oReal time requirements oPredicting yesterday's weather 2. Non-computable !3. Don't know the algorithm Complexity, N Time Space Tractable and IntractableCompSci 100E34.2On the Limits of ComputingIntractable 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! oLayers of look-ahead: If I do this, then he does this, .... oProblem Solved (?!) Can Represent Possibilities by Tree Assume 10 Possibilities Each Move t = A * 10^N or O(AN) Exponential ! ! !CompSci 100E34.3Exponential AlgorithmsRecognizing Exponential GrowthThings get BIG very rapidlyNumbers seem to EXPLODE KEY: at each added step, work multiplies rather than addsExponential = O(AN) = IntractableTraveling Salesperson ExampleVisit N Cities in Optimal Order Optimize for minimum: oTime oDistance oCost 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 100E34.4Traveling Salesperson Examples3 cities 2! = 2 possible routes (1 of interest)abcacb4 cities 3! = 6 possible routes (3 of interest)abcd abdcacbd acdbadbcadcb(Only half usually of interest because just reverse of another path)CompSci 100E34.5Traveling Salesperson Examples5 cities 4! = 24 possible routes abcde abced abdce abdec abecd abedc acbde acbedacdbe acdeb acebd acedb (12 of interest)adbce adbec adcbe adcebadebc adecb aebcdaebdcaecbdaecdbaedbcaedcbCompSci 100E34.6Towers of Hanoi N t t = 0.00549 * 2N 5 .17 sec (for a very old PC)10 5.62 sec 15 3.00 min 20 1.6 hour 25 2.13 day30 68.23 day 35 5.98 year What would a faster computer40 191.3 year do for these numbers?45 6120 year50 196 K year 55 6.27 M year60 201 M year65 6.42 G year 70 205 G yearCompSci 100E34.7Intractable AlgorithmsOther Games More hardware not the answer! Predicting Yesterday's Weather Actual Examples for Time ComplexityCompSci 100E34.8Existence of Noncomputable FunctionsApproachMatching 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 Mapping int to intHow 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 100E34.9Table of All Integer to Integer Functions1 1 2 6 0 0 8 2 1 4 . . 2 4 4 7 0 1 8 4 1 7 . . 3 9 6 8 0 0 8 6 2 10 . . 4 16 8 9 1 1 8 16 3 13 . . 5 25 10 10 1 0 8 10 5 16 . . 6 36 12 11 1 1 8 36 8 19 . . 7 49 14 12 1 0 8 14 13 22 . .8 64 16 13 1 1 8 64 21 25 . .9 81 18 14 1 0 8 18 34 28 . . . . . . . . . . . . . . . . . . . . . . . . . .CompSci 100E34.10A Function NOT in this (inclusive?) Table 1+1 1 2 6 0 0 8 2 1 4 . . 2 4+1 4 7 0 1 8 4 1 7 . . 3 9 6+1 8 0 0 8 6 2 10 . . 4 16 8 9+1 1 1 8 16 3 13 . . 5 25 10 10 1+1 0 8 10 5 16 . . 6 36 12 11 1 1+1 8 36 8 19 . . 7 49 14 12 1 0 8+114 13 22 . . 8 64 16 13 1 1 8 64+121 25 . . 9 81 18 14 1 0 8 18 34+128 . . 10 100 20 15 1 1 8 100 55 31+1 . . . . . . . . . . . . . .. . . . . . . . . . . .CompSci 100E34.11Existance of Noncomputable FunctionsAll 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 producePossible example: true random generator(No algorithm can produce truly random number sequence)Use Table Program must be of finite size; Requires infinite tableCompSci 100E34.12Noncomputable ProgramsPrograms 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 100E34.13The Halting Problem: Does it Halt? Consider Following Program: Does it halt for all possible input values to k? // input an integer value for k while (k > 1) { if ((k/2) * 2 == k) // is k even? k = k / 2; else k = 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 100E34.14Proving NoncomputabilityMathematicians 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 100E34.15Noncomputability ProofAssume Existence of Function halt: String halt(String p, String
View Full Document
Unlocking...