Chapter 12: Theory of Computation PDF

Chapter 12: Theory of Computation Computer Science: An Overview Eleventh Edition by J. Glenn Brookshear Copyright © 2012 Pearson Education, Inc.  Functions Funct...

Chapter 12: Theory of Computation Computer Science: An Overview Eleventh Edition by J. Glenn Brookshear Copyright © 2012 Pearson Education, Inc.  Functions 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 output Copyright © 2012 Pearson Education, Inc. 0-2  Functions (continued) Computing a function: Determining the output value associated with a given set of input values Non-computable function: A function that cannot be computed by any algorithm Copyright © 2012 Pearson Education, Inc. 0-3  Figure 12.1 An attempt to display the function that converts measurements in yards into meters Copyright © 2012 Pearson Education, Inc. 0-4  Figure 12.2 The components of a Turing machine Copyright © 2012 Pearson Education, Inc. 0-5  Turing 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 state Copyright © 2012 Pearson Education, Inc. 0-6  Figure 12.3 A Turing machine for incrementing a value Copyright © 2012 Pearson Education, Inc. 0-7  Incrementing the tape by 1 Copyright © 2012 Pearson Education, Inc. 0-8  Incrementing the tape by 1 (Cont…) Copyright © 2012 Pearson Education, Inc. 0-9  Incrementing the tape by 1 (Cont…) Copyright © 2012 Pearson Education, Inc. 0-10  Incrementing the tape by 1 (Cont…) Copyright © 2012 Pearson Education, Inc. 0-11  Incrementing the tape by 1 (Cont…) Copyright © 2012 Pearson Education, Inc. 0-12  Incrementing the tape by 1 (Cont…) Copyright © 2012 Pearson Education, Inc. 0-13  Church-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-14  Universal Programming Language A language with which a solution to any computable function can be expressed – Examples: “Bare Bones” and most popular programming languages Copyright © 2012 Pearson Education, Inc. 0-15  The 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-16  Figure 12.4 A Bare Bones program for computing X x Y Copyright © 2012 Pearson Education, Inc. 0-17  Figure 12.5 A Bare Bones implementation of the instruction “copy Today to Tomorrow” Copyright © 2012 Pearson Education, Inc. 0-18  The 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-19  Figure 12.6 Testing a program for self-termination Copyright © 2012 Pearson Education, Inc. 0-20  Figure 12.7 Proving the unsolvability of the halting program Copyright © 2012 Pearson Education, Inc. 0-21  Public-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 numbers Copyright © 2012 Pearson Education, Inc. 0-22  Figure 12.13 Public key cryptography Copyright © 2012 Pearson Education, Inc. 0-23  Encryption via Knapsack Problem Problem of selecting numbers from a collection to get a particular value. Given the list below: 191 691 573 337 365 730 651 493 177 354 Select a collection of values whose sum is 2063. Copyright © 2012 Pearson Education, Inc. 0-24  Encryption via Knapsack Problem Cont. Another way to encrypt a message: – Represent the message as a string of bits. – Break the string into segments of 10 bits each. – Represent each 10-bit segment by a number. Encrypt the message 100110000110011010 Copyright © 2012 Pearson Education, Inc. 0-25  Encryption via Knapsack Problem Cont. 100110000110011010 Copyright © 2012 Pearson Education, Inc. 0-26  Encryption via Knapsack Problem Cont. 0010011010 would represent 2131 (573 + 730 + 651 + 177) Therefore 100110000110011010 would be encrypted into two-number sequence 1247 and 2131. Copyright © 2012 Pearson Education, Inc. 0-27  Simplifying the decryption (Easy Knapsack) 1 4 6 12 24 51 105 210 421 850 Each number is larger than the sum of the preceding numbers. Find values whose sum is 995 Copyright © 2012 Pearson Education, Inc. 0-28  Hard Knapsack problem Uses three “magic” numbers. Example – using the magic numbers: 642, 2311 and 18. Copyright © 2012 Pearson Education, Inc. 0-29  Hard Knapsack problem (Cont.) Firstly, convert the list 1 4 6 12 24 51 105 210 421 850 Multiplying each entry by 642 (First number) Divide the products by 2311 (Second number), and record the remainder. Copyright © 2012 Pearson Education, Inc. 0-30  Hard Knapsack problem (Cont.) Resulting list is 642 257 1541 771 2184 388 391 782 2206 304 Given any target sum, multiply it by 18 (third number). Divide the product by 2311 (second number) and record the remainder Copyright © 2012 Pearson Education, Inc. 0-31  Hard Knapsack problem (Cont.) Use the remainder as target sum in the original easy knapsack system. Suppose the target sum is 4895. Copyright © 2012 Pearson Education, Inc. 0-32  Easy Knapsack system 1 4 6 12 24 51 105 210 421 850 Hard Knapsack system 642 257 1541 771 2184 388 391 782 2206 304 Copyright © 2012 Pearson Education, Inc. 0-33  Modular Arithmetic Modular arithmetic system is a system obtained by substituting each integer with the remainder obtained by dividing the integer in the list with a predetermined value. Copyright © 2012 Pearson Education, Inc. 0-34  Modular Arithmetic (Cont.) Given 0 1 2 3 4 5 6 7 8 9…. And a modulus of 7, the list will translate to 0 1 2 3 4 5 6 0 1 2 …. We use x (mod m) to denote the remainder of dividing x with m. Integers with same remainder when divided by m are said to be equivalent modulo m. Copyright © 2012 Pearson Education, Inc. 0-35  Modular Arithmetic (Cont.) Copyright © 2012 Pearson Education, Inc. 0-36  Encryption We need the modulus which must be greater than the sum of all the values in the list. X and Y which are multiplicative inverses in modulo m. Copyright © 2012 Pearson Education, Inc. 0-37  Encryption (Cont.) Given the list 1 4 6 12 24 51 105 210 421 850 With the sum of all the value equal 1685. Let m = 2311 x = 642 y = 18 Copyright © 2012 Pearson Education, Inc. 0-38  Encryption (Cont.) Multiply each entry by x (642) and record the remainder obtained by dividing by m (2311). 642 257 1541 771 2184 388 391 782 2206 304 The target sum is 4507. Copyright © 2012 Pearson Education, Inc. 0-39  Encryption (Cont.) Multiply the target sum (4507) by y (18) and divide the product by m (2311) Record the remainder…. Copyright © 2012 Pearson Education, Inc. 0-40 Copyright © 2012 Pearson Education, Inc. 0-41