PowerPoint PresentationChapter 12: Theory of ComputationFunctionsFunctions (continued)Figure 12.1 An attempt to display the function that converts measurements in yards into metersFigure 12.2 The components of a Turing machineTuring Machine OperationFigure 12.3 A Turing machine for incrementing a valueChurch-Turing ThesisUniversal Programming LanguageThe Bare Bones LanguageFigure 12.4 A Bare Bones program for computing X x YFigure 12.5 A Bare Bones implementation of the instruction “copy Today to Tomorrow”The Halting ProblemFigure 12.6 Testing a program for self-terminationFigure 12.7 Proving the unsolvability of the halting programComplexity of ProblemsFigure 12.8 A procedure MergeLists for merging two listsFigure 12.9 The merge sort algorithm implemented as a procedure MergeSortFigure 12.10 The hierarchy of problems generated by the merge sort algorithmFigure 12.11 Graphs of the mathematical expressions n, lg n, n lg n, and n2P versus NPFigure 12.12 A graphic summation of the problem classificationPublic-Key CryptographyEncrypting the Message 10111Decrypting the Message 100Figure 12.13 Public key cryptographyFigure 12.14 Establishing an RSA public key encryption systemCopyright © 2012 Pearson Education, Inc. Chapter 12:Theory of ComputationComputer Science: An OverviewEleventh Editionby J. Glenn BrookshearCopyright © 2012 Pearson Education, Inc. 0-2Chapter 12: Theory of Computation•12.1 Functions and Their Computation•12.2 Turing Machines•12.3 Universal Programming Languages•12.4 A Noncomputable Function•12.5 Complexity of Problems•12.6 Public-Key CryptographyCopyright © 2012 Pearson Education, Inc. 0-3Functions•Function: A correspondence between a collection of possible input values and a collection of possible output values so that each possible input is assigned a single outputCopyright © 2012 Pearson Education, Inc. 0-4Functions (continued)•Computing a function: Determining the output value associated with a given set of input values•Noncomputable function: A function that cannot be computed by any algorithmCopyright © 2012 Pearson Education, Inc. 0-5Figure 12.1 An attempt to display the function that converts measurements in yards into metersCopyright © 2012 Pearson Education, Inc. 0-6Figure 12.2 The components of a Turing machineCopyright © 2012 Pearson Education, Inc. 0-7Turing Machine Operation•Inputs at each step–State–Value at current tape position•Actions at each step–Write a value at current tape position–Move read/write head–Change stateCopyright © 2012 Pearson Education, Inc. 0-8Figure 12.3 A Turing machine for incrementing a valueCopyright © 2012 Pearson Education, Inc. 0-9Church-Turing Thesis•The functions that are computable by a Turing machine are exactly the functions that can be computed by any algorithmic means.Copyright © 2012 Pearson Education, Inc. 0-10Universal Programming LanguageA language with which a solution to any computable function can be expressed–Examples: “Bare Bones” and most popular programming languagesCopyright © 2012 Pearson Education, Inc. 0-11The Bare Bones Language•Bare Bones is a simple, yet universal language.•Statements–clear name;–incr name;–decr name;–while name not 0 do; … end;Copyright © 2012 Pearson Education, Inc. 0-12Figure 12.4 A Bare Bones program for computing X x YCopyright © 2012 Pearson Education, Inc. 0-13Figure 12.5 A Bare Bones implementation of the instruction “copy Today to Tomorrow”Copyright © 2012 Pearson Education, Inc. 0-14The Halting Problem•Given the encoded version of any program, return 1 if the program is self-terminating, or 0 if the program is not.Copyright © 2012 Pearson Education, Inc. 0-15Figure 12.6 Testing a program for self-terminationCopyright © 2012 Pearson Education, Inc. 0-16Figure 12.7 Proving the unsolvability of the halting programCopyright © 2012 Pearson Education, Inc. 0-17Complexity of Problems•Time Complexity: The number of instruction executions required–Unless otherwise noted, “complexity” means “time complexity.”•A problem is in class O(f(n)) if it can be solved by an algorithm in (f(n)).•A problem is in class (f(n)) if the best algorithm to solve it is in class (f(n)).Copyright © 2012 Pearson Education, Inc. 0-18Figure 12.8 A procedure MergeLists for merging two listsCopyright © 2012 Pearson Education, Inc. 0-19Figure 12.9 The merge sort algorithm implemented as a procedure MergeSortCopyright © 2012 Pearson Education, Inc. 0-20Figure 12.10 The hierarchy of problems generated by the merge sort algorithmCopyright © 2012 Pearson Education, Inc. 0-21Figure 12.11 Graphs of the mathematical expressions n, lg n, n lg n, and n2Copyright © 2012 Pearson Education, Inc. 0-22P versus NP•Class P: All problems in any class (f(n)), where f(n) is a polynomial•Class NP: All problems that can be solved by a nondeterministic algorithm in polynomial timeNondeterministic algorithm = an “algorithm” whose steps may not be uniquely and completely determined by the process state•Whether the class NP is bigger than class P is currently unknown.Copyright © 2012 Pearson Education, Inc. 0-23Figure 12.12 A graphic summation of the problem classificationCopyright © 2012 Pearson Education, Inc. 0-24Public-Key Cryptography•Key: A value used to encrypt or decrypt a message–Public key: Used to encrypt messages–Private key: Used to decrypt messages•RSA: A popular public key cryptographic algorithm–Relies on the (presumed) intractability of the problem of factoring large numbersCopyright © 2012 Pearson Education, Inc. 0-25Encrypting the Message 10111•Encrypting keys: n = 91 and e = 5•10111two = 23ten•23e = 235 = 6,436,343•6,436,343 ÷ 91 has a remainder of 4•4ten = 100two•Therefore, encrypted version of 10111 is 100.Copyright © 2012 Pearson Education, Inc. 0-26Decrypting the Message 100•Decrypting keys: d = 29, n = 91•100two = 4ten•4d = 429 = 288,230,376,151,711,744•288,230,376,151,711,744 ÷ 91 has a remainder of 23•23ten = 10111two•Therefore, decrypted version of 100 is 10111.Copyright © 2012 Pearson Education, Inc. 0-27Figure 12.13 Public key cryptographyCopyright © 2012 Pearson Education, Inc. 0-28Figure 12.14 Establishing an RSA public key encryption